Эквивалентность формул. Тавтологии и противоречия

Поскольку для одной и той же функции существует бесконечно много формул, соответствующих ей, то для формул введено понятие эквивалентности. Формулы F₁ и F₂ эквивалентны (равносильны), если реализуемые ими функции совпадают, т.е. имеют одни и те же значения истинности на одинаковых наборах переменных. Практически это означает, что векторы истинности f (F ₁) и f (F ₂) совпадают.

Пример 1. Проверить эквивалентность F ₁= х Ú` у и F <sub>2</sub>=` х & у.

Решение. Строим таблицы истинности функций f (F ₁) и f (F ₂).

x	y	F 1	F 2

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

Ответ: формулы неэквивалентны.

Пример 2. Проверить эквивалентность F ₁= х Ú `у и F <sub>2</sub>= Ø(`х & у).

Решение. Строим таблицы истинности функций f (F ₁) и f (F ₂).

x	y	F 1	F 2

Ответ: векторы истинности f (F ₁) и f (F ₂) совпадают, формулы эквивалентны.

Пример 3. Какие из предложенных ниже формул эквивалентны формуле F ₁= х Å(у ® хz): 1) Ø(х Ú у)Ú ху`z; 2) (х Å у)® хуz; 3) (х Ú у Ú z)&Ø(х Å у).

Решение. Строим таблицу истинности функции f (F ₁), а затем для всех вариантов формул 1), 2) и 3):

x	y	z	F 1	1)	2)	3)

Сравнение векторов истинности показывает, что эквивалентной заданной формуле F ₁= х Å(у ® хz) является формула 1), поскольку у них одинаковые векторы истинности. Формулы 2) и 3) не эквивалентны F ₁.

Ответ:1).

Особое место в логике занимают формулы, эквивалентные тождественной единице. Это тождественно истинные формулы, которые задают всегда правильные (независимо от значений входящих в них переменных) рассуждения. У них в векторе истинности должны стоять одни единицы. Их противоположностью являются тождественно ложные формулы, у которых в векторе истинности стоят только нули.

Тождественно истинные формулы также называют тавтологиями, тождественно ложные – противоречиями. Поскольку в математике формулы и утверждения, всегда истинные независимо от значений входящих в них объектов, называют теоремами, то термин “тавтология” - это специальное название для теорем в логике.

Пример 4. Выяснить, будут ли тавтологиями формулы:

1) F ₁= х Ú `х Ú `у, 2) F ₂=(x ½ у)Å xу, 3) F ₃ =xу Å(х Ú у).

Решение. Из нижеприведенных таблиц истинности для функций, реализующих формулы F ₁, F ₂ и F ₃, следует, что формулы F ₁, F ₂ – тождественно истинные, поскольку векторы истинности у них состоят только из единиц, а F ₃не является таковой, так как соответствующий ей вектор истинности имеет нули.

x	y	F 1	F 2	F 3

Пример 5. Выяснить, какие из перечисленных формул будут противоречиями: 1) F ₁=(х Å у)(х Å z); 2) F ₂ =xуz &(` х Ú` у Ú` z); 3) F ₃=(х ® уz)ÅØ х.

Решение. Строим таблицу истинности функций, реализующих формулы F ₁ ,F ₂, F ₃.

x	y	z	1)	2)	3)

Анализ векторов истинности показывает, что все нули стоят только в векторе, соответствующем второму варианту формулы, следовательно, она является тождественно ложной.

Ответ: 2).

Пример 6. Какое логическое выражение равносильно выражению F =Ø(Ø А ÚØ В)Ù С: 1) Ø А Ú В ÚØ С 2) А Ù В Ù С 3) (А Ú В)Ù С 4) (Ø А ÙØ В)ÚØ С?

Решение. Решение можно найти, построив полную таблицу истинности для функций, реализующих заданное выражение F и выражения F ₁- F ₄, стоящие в вариантах ответа 1)-4), и сравнив соответствующие векторы истинности.

Однако меньше затрат требует решение, основанное на последовательной проверке наборов значений переменных А, В, С и отбрасывании неподходящих вариантов ответа.

N =0. А =0, В =0, С =0. F (0,0,0) = Ø(Ø0ÚØ0)Ù0 = Ø(1Ú1)Ù0 =0Ù0 =0.

F ₁(0,0,0) = Ø0Ú0ÚØ0 = 1Ú0Ú1 = 1. Так как F ₁(0,0,0)¹ F (0,0,0), то вариант ответа 1) сразу отбрасываем;

F ₂(0,0,0) = 0Ù0Ù0 = 0; F ₃(0,0,0) = (0Ú0)Ù0 =0Ù0=0;

F ₄(0,0,0) = (Ø0ÙØ0)ÚØ 0 = 1Ú1=1 – вариант ответа 4) также отбрасываем.

N =1. А =0, В =0, С =1. Проверяем только варианты 2) и 3)

F (0,0,1) = Ø(Ø0ÚØ0)Ù1 = Ø(1Ú1)Ù1 =0Ù1 =0;

F ₂(0,0,1) = 0Ù0Ù1 = 0; F ₃(0,0,1) = (0Ú0)Ù1 =0Ù1=0;

N =2. А =0, В =1, С =0. Проверяем только варианты 2) и 3)

F (0,1,0) = Ø(Ø0ÚØ1)Ù0 = Ø(1Ú0)Ù0 =0Ù0 =0;

F ₂(0,1,0) = 0Ù1Ù0 = 0; F ₃(0,1,0) = (0Ú1)Ù0 =0Ù0=0;

N =3. А =0, В =1, С =1. Проверяем только варианты 2) и 3)

F (0,1,1) = Ø(Ø0ÚØ1)Ù1 = Ø(1Ú0)Ù1 =0Ù1 =0;

F ₂(0,1,1) = 0Ù1Ù1 = 0; F ₃(0,1,1) = (0Ú1)Ù1 =1Ù1=1– вариант ответа 3) отбрасываем.

На остальных наборах проверяем только вариант 2).

N =4. А =1, В =0, С =0. F (1,0,0) = Ø(Ø1ÚØ0)Ù0 = Ø(0Ú1)Ù0 =0Ù0 =0;

F ₂(1,0,0) = 1Ù0Ù0 = 0.

N =5. А =1, В =0, С =1. F (1,0,1) = Ø(Ø1ÚØ0)Ù1 = Ø(0Ú1)Ù1 =0Ù1 =0;

F ₂(1,0,1) = 1Ù0Ù1 = 0.

N =6. А =1, В =1, С =0. F (1,1,0) = Ø(Ø1ÚØ1)Ù0 = Ø(0Ú0)Ù0 =1Ù0 =0;

F ₂(1,1,0) = 1Ù1Ù0 = 0.

N =7. А =1, В =1, С =1. F (1,1,1) = Ø(Ø1ÚØ1)Ù1 = Ø(0Ú0)Ù1 =1Ù1 =1;

F ₂(1,1,1) = 1Ù1Ù1 = 1.

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

Ответ: 2).

Дата добавления: 2014-01-20