2. Приведем решение задачи 2.1. Рассмотрим высказывания: Х=«профсоюзы будут поддерживать губернатора», Y=«губернатор подпишет закон», U=«фермеры окажут губернатору поддержку», V=«губернатор наложит вето». Тогда рассуждение 2.1 представимо формулами F₁=Y®X, F₂=V®U, F₃=(ØY&V)Ú(Y&ØV), G=ØXÚØY.

3. Тождественно истинны формулы а,в,ж и з. Остальные формулы тождественно истинными не являются.

4. В случаях а и б ответ положительный, в качестве F можно соответственно взять X&Y и Y. В случае в ответ отрицательный. Действительно, если интерпретация j такова, что j(Y)=1, j(Z)=0, то j(G)=0 независимо от j(F).

5. В случаях б и г формулы равносильны, в остальных нет.

6. Приведем решение задачи в случае г. Обозначим формулу Ø[(X&Y)ÚØZ] буквой F, а формулу Ø(Z®X)ÚØ(Z®Y) буквой G. Для доказательства равносильности надо из одной формулы с помощью законов логики высказываний получить другую. Применим к формуле F последовательно законы 18 и 17, получим формулу

F₁=(ØXÚØY)&Z

Далее, используя дистрибутивность (закон 11), получим формулу

F₂=(ØX&Z)Ú(ØY&Z).

Осталось отметить, что формула ØX&Z равносильна Ø(Z®X) (законы 19,18 и 20), а формула ØY&Z равносильна Ø(Z®Y). Следовательно, F равносильна G.

7. Приведем решение задачи 7а. Отметим вначале, что логичность следствия можно доказать, построив совместную таблицу истинности формул F₁,F₂,F₃ и G, и убедиться в том, как только все формулы F₁,F₂,F₃ принимают значение 1, то формула G принимает то же значение 1. Однако таблица будет довольно громоздкой, у нее будет 16 строк. Применим другой способ решения задачти. Предположим противное, пусть существует интерпретация j такая, что j(F₁)=j(F₂)=j(F₃)=1, и j(G)=0. Тогда j(X)=1 и j(Y)=0, поскольку j(G)=0, и j(W)=0, поскольку j(F₃)=1. Далее из равенств j(F₂)=j(Z®W)=1 и j(W)=0 следует, что j(Z)=0. Но тогда j(F₁)=j(X®YÚZ)=0, что противоречит условию j(F₁)=1. Противоречие указывает, что G есть логическое следствие F₁,F₂, и F₃.

8. Для решения задачи необходимо найти интерпретацию, при которой формулы F₁,…,F_n, истинны, а G ложны. Такими интерпретациями являются

а) j(X)=j(Z)=1, j(Y)=j(W)=0;

б) j(X)=j(Y)=j(Z)=j(Z₂)=1, j(Z₁)=0;

в) j(X)=j(X₁)=j(Y)=j(Y₁)=0, j(Z)=1.

9. Рассуждения из задач 2.2 и 2.3 логично, а из задачи 2.4 – нелогично.

10. Приведем решение задачи 10.1. Рассмотрим высказывания: X=«Джонс не встречал Смита», Y=«Смит был убийцей», Z=«Джонс лжет», U=«убийство произошло после полуночи». Тогда рассуждения можно представить последовательностью формул: F₁=X®YÚZ, F₂=ØX&U, F₃=U®YÚZ, F₄=ØU, G=X. Существует интерпретация j такая, что j(F₁)=j(F₂)=j(F₃)=j(F₄)=1, j(G)=0, пример, j(X)=j(U)=0, j(Y)=j(Z)=1. Это означает, что G не является логическим следствием формул F₁,…,F₄ и что рассуждение нелогично.

Рассуждения из задач 10.2 – 10.4 также нелогичны.

11. Указание. Применить алгоритм приведения к ДНФ.

12. Указание. Применить алгоритм приведения к СДНФ.

13. Указание. Применить алгоритм приведения к КНФ.

14. Эквивалентные простые схемы приведены на следующих рисунках:

а)

б)

в)

15. Приведем решение задачи. Рассмотрим формулу F(X₁,X₂,X₃), имеющую следующую таблицу истинности

Атомарные формулы X₁,X₂ и Х₃ обозначают выключатели. Заметим, что в таблице истинности значения атомарных формул X₁,X₂ и Х₃ в каждой следующей строке отличаются от предыдущей только одной из атомарных формул, а значение формулы F меняется на противоположное. Это отражает требование о том, чтобы при нажатии на любой из выключателей свет выключался, если он был включен, и включался, если он был выключен.

По таблице истинности выпишем формулу F:

F=(X&Y&Z)Ú(X&ØY&ØZ)Ú(ØX&ØY&Z)Ú(ØZ&Y&ØZ).

Найдем наиболее простую формулу G равносильную F, в запись которой входят лишь связки &,Ú и Ø:

G=[X&((Y&Z)Ú(ØY&ØZ))]Ú[ØX&((ØY&Z)Ú(Y&ØZ))].

По формуле G построим искомую схему

16. Указание. Рассмотреть формулу F(X₁,X₂,X₃), таблица истинности которой получается в соответствие с формулой

j(F)=max {j(X₁),j(X₂),j(X₃)}.

По таблице истинности, выписать формулу в совершенной дизъюнктивной нормальной форме. Затем упростить ее и по упрощенной формуле составить схему так, как это сделано в решении предыдущей задачи.