Высказывания и булевы функции

Высказывания и булевы функции. Одной из основных задач алгебры высказываний является установление значения истинности сложных высказываний в зависимости от значения истинности входящих в них простых высказываний.

Для этого целесообразно рассматривать сложные высказывания как функции входящих в них простых высказываний. С другой стороны, так как значение истинности и или л сложного высказывания зависит по определению логических связок не от самих простых высказываний, а лишь от их значения истинности, то можно считать, что любое сложное высказывание определяет функцию, аргументы которой независимо друг от друга принимают значения и или л, а значение самой функции также принадлежит множеству и, л конечно, существенно не то, что речь идет о функциях от нескольких аргументов из множества и, л в множество и, л , а лишь то, что данные множества двухэлементны.

Эти множества зачастую обозначают не через и, л , а, например, через 0, 1 , считая, что 1 означает истину, а 0 - ложь. Такие функции называются булевыми функциями по имени Д. Буля. Например, формула F а, b, с а b с а описывает, учитывая определение входящих в нее связок, булеву функцию, задаваемую следующей таблицей а b с F a, b, с а b с F a, b, с и и и и л и и и и и л л л и л и и л и и л л и и и л л и л л л и Заметим, что булевых функций от n аргументов имеется лишь конечное число, а именно столько, сколько возможно функциональных таблиц.

Число возможных наборов аргументов равно 2n, а каждому набору аргументов можно независимо друг от друга сопоставлять одно из значений и или л. Таким образом, число всевозможных булевых функций от n аргументов равно - Оно очень быстро растет с ростом n. Изучение свойств булевых функций имеет большее значение как для алгебры и математической логики, так и для их приложений в кибернетике и теории автоматов.

Естественно распространить определение высказывательных связок, так как мы их определили выше, на булевы функции. Мы ограничимся рассмотрением лишь связок называемых булевыми связками или булевыми операциями. Такое ограничение оправдано тем, что, как легко проверить, связки и могут быть выражены через другие булевы связки.

При помощи таблиц истинности, приведенных выше, легко проверяются следующие тождества a b a b a b a b a b, которые позволяют повсеместно заменить связки, на Если мы теперь имеем булевы функции F xl, х2 хn , G х1, х2 хn от n переменных, то действие связок над ними определяется естественным образом F xl, x2 хn G х1, x2 хn , F xl, x2, ,хn G xl, x2 хn , F xl, x2 хn - это такие булевы функции, которые принимают значения, предписываемые соответствующими таблицами для каждого возможного значения аргументов.

Кратко булевы операции так переносятся на булевы функции, как действия арифметики переносятся на обычные функции числовых аргументов. Вообще имеет место далеко идущая аналогия между обычной алгеброй чисел и числовыми функциями, с одной стороны, и высказываниями и булевыми функциями - с другой.

При этом можно отметить, что в одном определенном смысле алгебра булевых функций проще алгебры числовых функций если рассматривать лишь функции некоторого конечного числа аргументов, то таких функций лишь конечное число. Поэтому выкладки с булевыми функциями вполне доступны пониманию школьников старших классов. Естественно, закономерности булевой алгебры менее привычны и вызывают удивление и недоверие это судьба всякого новшества. Выпишем законы булевой алгебры. Большими латинскими буквами А, В X, Y, Z мы обозначим объекты, над которыми осуществляются булевы операции Для определенности будем считать, что эти объекты - булевы функции некоторого фиксированного числа переменных.

Среди них есть два особых элемента 1, 0. Это соответственно функции, принимающие для всех аргументов значения 0 и 1 постоянные функции - нуль и единица. Тогда А В В А, A B B A A В C А В C A В C А В C A A A A A A A 1 A A 1 A A 0 0 A 0 A A B A B A B A B A B C A B A C A B C A B A C A A Если, как это обычно делают, булевы операции считать аналогом сложения, умножения и перехода к противоположному числу, то некоторые из вышеприведенных законов те же, что для числового сложения и умножения, другие же существенно отличаются от привычных. 4.1.3 Задания для учащихся. 1. Верно ли высказывание 205 кратно 5 77 8 10 133. 2. А - множество точек треугольника и В - множество точек четырехугольника. Верно ли высказывание CA CB KB KA SB SA SA SB? 3. Известно, что А и, В и, Х л, Y л. Найдите значение высказывания АХ YA AX ВY AB X XB Y XA YB AX YX . 4. Составьте таблицу истинности высказываний ХХ ХY Y XY X XY XY Y. 5. Используя переменные X, Y, Z, запишите сочетательное свойство операции и . 6. Проверьте равенство XY Z XZ YZ и XY Z XZ YZ , составляя таблицы истинности для левой и правой части. 4.2