Дискретная математика

60 Примером тавтологии является формула xvlx, в чем легко убедиться, составив таблицу истинности. Другие примеры тавтологий; х^х , ( x ^ ) s (у^). N/ Формула, тождественно равная нулю, называется противоречием. Примеры противоречий: х& 1х, ](х=>х), х=1х. Очевидно, что формула А является тавтологией тогда и только тогда, когда 1А есть противоречие. Тавтологию будем обозначать через Г, а противоречие - через П. Легко доказать следующую теорему. Теорема 3.1. Если А есть тавтология, содержащая переменные xi, Х2,.-; х„, и В получается из А подстановкой в А произвольных формул Аь А2,-- вместо переменных xi, Х2,..., х„ соответственно, то В есть тавтология, т.е. подстановка в тавтологию приводит к тавтологии. jlj Формула называется выполнимой, если она принимает значения 1 хо т я 1 бы для одной совокупности значений переменных, в нее входящих. Например, х&у является выполнимой формулой, так как принимает значения 1, когда .х=1 и>'=1, а формула xcfe/л не будет выполнимой, так как всегда равна нулю. Очевидно, что формула А выполнима тогда и только тогда, когда А не является противоречием. Докажем следуЕощ>то теорему. Теорема 3.2. Формулы А ш В равносильны тогда и только тогда, когда является тавтологией. Доказательство. Необходимость. Пусть /1 и S равносильны, следовательно, они при каждой совокупности значений всех переменных, входящих в них, принимают одинаковые значения, тогда по определению операции = формула А^В всегда принимает значение 1, т.е. является тавтологией. Достаточность. Пусть А=В тавтология, т.е. принимает всегда значение 1. Это означает, что А и В имеют всегда одинаковые значения, т.е. они равносильны. Теорема доказана. § 5. Важнейшие пары равносильных формул Пусть X, у и Z - булевы переменные, Т - тавтология и 77 - противоречие. Используя таблицу истинности, легко показать: 1) равносильно.V,