Преобразование логических выражений

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

Основные формулы преобразования логических выражений:

Основные формулы преобразования логических выражений (продолжение)

Пример1: Упростить логическую формулу:
В скобках указан номер формулы, по которой было преобразование

Пример 2
Переведите к виду логической формулы высказывание: «Неверно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра».
Решение. Определим следующие простые высказывания:
П — «пасмурная погода»;
Д — «идет дождь»;
В — «дует ветер».
Тогда соответствующее логическое выражение запишется в виде:

Пример 3
Кто из учеников А, В, С и D играет, а кто - не играет в шахматы, если известно следующее:
а) если А или В играет, то С не играет;
б) если В не играет, то играют С и D;
в) С играет?
Решение. Определим следующие простые высказывания:
А — «ученик А играет в шахматы»;
В — «ученик В играет в шахматы»;
С — «ученик С играет в шахматы»;
D — «ученик D играет в шахматы».
Запишем сложные высказывания, выражающие известные факты:

Решение:
Ответ: в шахматы играют ученики С и D, а ученики А и В — не играют.
(АvВ)→¬С=

Задача 1
Упростите выражение, используя минимум законов логических операций:

Задача 2
Определите значение формул:

Задача 3
Определите, кто из подозреваемых участвовал в преступлении, если известно:
1) если Иванов не участвовал или Петров участвовал, то Сидоров участвовал;
2) если Иванов не участвовал, то Сидоров не участвовал.

Задача 4
Аня, Вика и Сергей решили пойти в кино. Учитель, хорошо знавший ребят, высказал предположения:
1) Аня пойдет в кино только тогда, когда пойдут Вика и Сергей;
2) Аня и Сергей пойдут в кино вместе или же оба останутся дома;
3) чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.
Когда ребята пошли в кино, оказалось, что учитель немного ошибся: из трех его утверждений истинными оказались только два.
Кто из ребят пошел в кино? Решить задачу с помощью логических операций.

ЕГЭ 2010г.
Какое логическое выражение равносильно выражению
¬(¬А v ¬В) ∧ С?
1) ¬А v В v ¬С
2) А ∧ В ∧ С
3) (A v В) ∧ С
4) (¬А ∧ ¬В) v ¬С