Законы логики

Минимизация логических выражений (функций)
Упражнения
1. Найдите значения выражений:
А) (1 V1) V (1V0) =
1
Б) (A V 1) V (b V 0)=
1
B) (0 & 1) & 1 =
0
Минимизация – это приведение логического выражения к кратчайшей форме, когда количество переменных и логических операций в выражении становится минимальным.
Г) ((1 & A) V (B & 0)) V 1 =
1
2. Вычислите:
А) 1 V x & 0 =
Б) x & x & 1 =
В) 0 & x V 0 =
Г) 0 V x & x =
1
x
0
x
3. Найдите х, если
4. Путём преобразований докажите равносильность следующих высказываний:

Решение примеров на минимизацию логических выражений и функций
1. (A + ¬B)(¬A + B) A B
2. A + A (B + ¬(A ¬(BC))) ¬(A C)
= A B
= A
3.(¬(A B) + ¬ B C) (¬A C + A + ¬ C)
= ¬ (A B)
4. ¬ (x ∨ a) ∨ ¬ (x ∨ ¬a)
= ¬ x
5. (ab ¬ c) ∨ abc ∨ ab
= ab
6. ¬(¬x ∨ ¬y) ∨ ¬x ¬(x ∨ ¬(¬x ∨ y))
= ¬ x + y

Логическое следование(импликация)
Логическое следование(импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…».
Пример: Р = Если число делится на 9, то оно делится на 3
Обозначение импликации: А → В; А ⇒ В
Говорят: если А, то В; А имплицирует В; А влечет В; В следует из А
Таблица истинности:
Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное (когда истинная предпосылка ведет к ложному выводу).

ЕГЭ 2006
A9
Для какого из указанных значений числа X истинно высказывание:
(X>4) \/ ((X>1) ⇒X>4))?
1)1 2)2 3)3 4)4
A10
Какое логическое выражение равносильно выражению
¬ (¬A \/ B) \/ ¬C?
1)(A /\ ¬B) \/ ¬C 2)¬A \/ B \/ ¬C 3)A \/ ¬B \/ ¬C 4)(¬A /\ B) \/ ¬C
A11
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности :
Какое выражение соответствует F?
1)¬X \/ ¬Y \/ ¬Z 2)X /\ ¬Y /\ ¬Z 3)X \/ Y \/ Z 4)X /\ Y /\ Z

ЕГЭ 2007
A9
Для какого числа X истинно высказывание
((X>3) \/(X<3)) → (X<1)
1)1 2)2 3)3 4)4
A10
Какое логическое выражение равносильно выражению ¬ (A /\ B) /\ ¬C?
1)¬A \/ B \/ ¬C 2)(¬A \/ ¬B) /\ ¬C 3)(¬A \/ ¬B) /\ C 4)¬A /\ ¬B /\ ¬C
A11
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
1)¬X \/ Y \/ ¬Z 2)X /\ Y /\ ¬Z 3)¬X /\ ¬Y /\ Z 4)X \/ ¬Y \/ Z

Решение логических задач
1. с помощью графов
Задача 1. В шашечном турнире каждый из ребят – Миша, Серёжа и Яша – защищал честь своего класса. Один из них учится в 10 А, другой – в 10 Б, третий - в 10 В классе. Первую партию играл Миша и ученик 10 А класса. Вторую – Серёжа с учеником 10 В класса, а Миша отдыхал. Кто за какой класс играл?
Дано:
Миша (М)
Серёжа (С)
Яша (Я)
Классы
10 А
10 Б
10 В
Надо:
Кто за какой класс играл?
Рассуждения:
М 10 А
С 10 Б
Я 10 В
Ответ: Сережа играл за 10 А класс,
Миша – за 10 Б класс,
Яша – за 10 В класс.

Задача 2. Перед началом Турнира Четырёх болельщики высказали следующие предположения по поводу своих кумиров:
А) Макс победит, Билл – второй;
В) Билл – третий, Ник – первый;
С) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на турнире заняли Джон, Ник, Билл, Макс?
(В ответе перечислите подряд без пробелов места участников в указанном порядке имён.)
Решение:
Макс 1
Билл 2
Ник 3
Джон 4
Противоречие!
Макс 1
Билл 2
Ник 3
Джон 4
Макс – 4 Билл – 2 Ник – 1 Джон - 3
Ответ: 3 1 2 4

Задача 3. В начале лета школьники организовали сельскохозяйственную бригаду и избрали бригадира, заместителя бригадира и звеньевых первого, второго и третьего звеньев. Их имена: Аня, Боря, Вася, Гриша и Дина. Звеньевая первого звена решила подружиться со звеньевой второго звена. Дина удивилась, узнав, что бригадир и звеньевая второго звена – брат и сестра. Гриша дружит с бригадиром и его заместителем. У Васи нет сестёр. Назовите должности каждого из ребят.
Ответ: Аня – звеньевая 2 звена
Боря - бригадир
Вася – заместитель бригадира
Гриша - звеньевой 3 звена
Дина - звеньевая 1 звена

2. с помощью таблиц
Задача 4. Корнеев, Докшин, Мареев и Скобелев –жители нашего города. Их профессии – пекарь, врач, инженер и милиционер.
Известно, что:
Корнеев и Докшин – соседи и всегда на работу ездят вместе;
Докшин старше Мареева;
Корнеев регулярно обыгрывает Скобелева в настольный теннис;
Пекарь на работу всегда ходит пешком;
Милиционер живёт не рядом с врачом;
Инженер и милиционер встречались один раз, когда милиционер оштрафовал инженера за нарушение правил уличного движения;
Милиционер старше врача и инженера.
Определите, кто чем занимается.

Фамилия
-
-
-
-
-
+
+
-
+
+
-