Спирина, М.С. Дискретная математика

таблицу и для п = 3, но тогда она содержала бы 2 8 = 256 столбцов, что технически невозможно реализовать. С другой стороны, фун­ кциям трех и более переменных соответствовали бы трехместные отношения и отношения более высоких порядков. Но природа устроена согласно принципу минимальной целесообразности: там, где это возможно, в частности в дискретных множествах, одно- и двухместные отношения являются достаточными для опи­ сания всех других. Далее будет показано, что все булевы функции выражаются в виде формул через уже знакомые функции одного и двух переменных. Соглашения о написании формул. Определены правила ком ­ пактной записи булевых функций и порядок их упрощения. • Внешние скобки не используются. • Действия в скобках выполняются в первую очередь. • Учитываются приоритеты логических операций в порядке воз­ растания: отрицание, следствие, конъюнкция, дизъюнкция. По аналогии с непрерывными функциями можно ввести ус­ ловное понятие элементарных булевых функций: отрицание, конъ­ юнкция, дизъюнкция, константы. Тогда некоторые известные эк ­ вивалентности можно объединить в свойства элементарных буле­ вых функций. Теперь можно описать законы логики на уже доступном языке булевых функций. В предисловии к этой главе указывались причи­ ны, побудившие нас говорить сначала об абстрактных символах О и 1 , а не об интуитивно знакомых, хотя и относительных поняти­ ях «истины» и «лжи». Далее символ 0 будет означать «ложь» (или отсутствие сигнала), а 1 — «истину». Тем самым мы в явном виде построили взаимно-однозначное соответствие между множеством В= { 0 , 1 } и множеством (истина, ложь}. 4.3. Сложные высказывания Рано или поздно всякая правиль­ ная математика находит применение в том или ином деле. А. Н. Крылов Сложные предложения в русском языке образуются из про­ стых путем связок (и, а, если... то и т.д.). Сложные высказывания в логике образуются из простых путем логических операций, соответствующих определенным связкам естественного языка. Истинность или ложность сложного суждения являются функ­ циями простых суждений, входящих в его состав. Зная истин­ ность простых суждений, можно установить истинность сложных суждений. 140