Тема 5. ЛОГИКА ВЫСКАЗЫВАНИЙ

1. Логика высказываний в структуре современной формальной логики. Язык логики высказываний. Основные задачи и методы построения логики высказываний. Табличный метод. Правильно построенные формулы (ППФ). Таблицы истинности. Тождественно истинные, тождественно ложные и выполнимые формулы.

2. Понятие разрешимости логической системы. Равносильные формулы. Метод приведения к нормальным формам. Конъюнктивная нормальная форма (КНФ). Выявление законов логики при помощи приведения формул к КНФ. Дизъюнктивная нормальная форма (ДНФ). Тождественно ложные формулы. Совершенные нормальные формы. Сокращенные нормальные формы. Исчисление высказываний.

 

Упражнения

 

1. Установите с помощью табличного метода, являются ли следующие формулы законами логики:

______

а) p & p¯

б) (( p ⊃ q) & q) ⊃ q

в) (( p ⊃ q) & r) ⊃ (( p v r) ⊃ q)

г) ((p& q‾) ⊃ r) ≡ (p ⊃ (q ⊃ r))

д) ((p ⊃ q) & q) ⊃ ‾p

2. Запишите в символическом виде и проверьте с помощью таблиц наличие следования:

а) если бы Петров знал решение задачи, он рассказал бы его Смирнову и Николаеву. Если Смирнов не знает решения, то Петров его знает, а если Смирнов знает, то Николаев не знает. Значит, только Смирнов знает решение задачи;

б) если число делится на 2 и на 3, то оно делится и на 6. Значит, если число делится на 2, а на 6 не делится, то оно не делится и на 3;

в) если в какой-то точке пространства возникло переменное магнитное поле, то оно не стоит на месте, а со скоростью света распространяется во все стороны;

3. Следующие формулы привести к нормальным формам:

____

а) (p v q) ⊃ ((p &q) ⊃ p)

б) ((p ⊃ q) ⊃ (q ⊃ p)) ⊃ (p v q)

в) (p ≡ q) ⊃ (p &q)

г) ((p ⊃ q) & (q ⊃ r)) ⊃ (p &q)

д) ((p ⊃ q) ⊃ r) ⊃ p

е) (p v (q ⊃ r)) ⊃ p

ж) ((p ⊃ q) & (q ⊃ r)) ⊃ (p ⊃ r)

з) (p& q) ⊃ ((p ⊃ q) ⊃ q)

и) ((q ⊃ r) ⊃ q) ⊃ (r ⊃ p)

к) ((p & q) v (p ⊃ r)) ⊃ (q & r)

л) (p ≡ q) ⊃ p

4. Приведите к КНФ формулы:

а) (p& q) ⊃ ((p ⊃ q) ⊃ q)

б) (p ⊃ q) ⊃ ((p v r) ⊃ (q v r))

в) (p & (q v r)) ⊃ (‾p ⊃ ‾r)

_____

г) (‾p & ‾q) ⊃ (p v q)

д) (‾p v (q ⊃ r)) v ((p ⊃ ‾r) ⊃ (p ⊃ ‾q ))

е) (p ⊃ q) ⊃ (q v (‾p ⊃ r))

 

5. Приведите к ДНФ формулы:

 

а) (p ⊃ r) & (q v r)

_____ _________

б) (p v r) & ((q & r) v p)

в) (p ⊃ q) & (‾p v q)

_____

г) (p v r) & (p ⊃ q)

д) (p & q) & ((q ⊃ p) & p)

6. При помощи таблицы истинности установить являются ли равносильными формулы:

а) (p ⊃ q) и (‾q ⊃ ‾p)

б) (p ⊃ q) и (‾p v q)

в) (p ⊃ (q ⊃ r)) и ((p & q) ⊃ r)

г) (p & (q v r)) и ((p & q) v (p & r))

д) (p v (q & r)) и ((p v q) & (p v r))

 

7. Используя в качестве разрешающей процедуры процесс приведения к КНФ, решите задачу.

 

Три цеха договорились, что при утверждении проектов должны соблюдаться следующие условия:

· Если второй цех не участвует в утверждении проекта, то в нем не участвует и первый цех.

· Если второй цех принимает участие в утверждении проекта, то в нем принимают участие первый и третий цеха.

· Обязан ли при этих условиях третий цех принимать участие в утверждение проекта, когда в нем принимает участие первый цех?