Решение логических задач

Логические функции одной переменной

Логические функции двух переменных

Логическое умножение
Коньюнкция
conjunctio – лат. – связываю
Соединение двух простых высказываний A и B в одно составное с помощью союза «и» (а, но) называют логическим умножением или конъюнкцией, а результат операции — логическим произведением.
Указание о логическом перемножении простых высказываний A и B обозначается так: AB, A∧B, A&B.

Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны.
Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. A∙B∙C=1, только если A=1, B=1, C=1.

Свойства конъюнкции

Логическое сложение
Дизъюнкция
disjunctio – лат. – различаю
Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в неисключающем смысле, называется логическим сложением или дизъюнкцией, а полученное составное высказывание — логической суммой.
Указание о необходимости выполнить логическое сложение высказываний A и B записывается так: A+B или A∨B.

Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны.
Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. A+B+C=0, только если A=0, B=0, C=0.

Свойства дизъюнкции

Логическое отрицание
Инверсия
inversio – лат. – переворачиваю
Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией или
Присоединение слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания
Указание выполнить логическое отрицание над высказыванием A записывается так:

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.
закон двойного отрицания

Логическое следование
Импликация
implicatio – лат. – тесно связываю
Логическое следование соответствует обороту «если…, то…», обозначается A⇒B или A→B.
Читается:
если А, то В;
из А следует В;
А имплицирует В;
А достаточно для В;
В необходимо для А;
А только тогда, когда В.

Высказывание A⇒B ложно в том и только в том случае, когда условие (первое высказывание A) истинно, а следствие (второе высказывание B) ложно.

Логическая равносильность
Эквиваленция
aequivalens – фр. – равноценное или равнозначное
соответствует оборотам речи:
«тогда и только тогда»
«в том и только в том случае»
обозначается A↔B или A≡B.

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

Сложение по модулю «2»
Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в исключающем смысле, называется
строгой дизъюнкцией,
сложение по модулю «2»,
исключающее «или».
Обозначается A⊕B.

Выражение A⊕B истинно в том и только в том случае, когда значения исходных высказываний не равны между собой.

Закон коммутативности
Переместительный закон
A+B=B+A
A∙B=B∙A

Сочетательный закон
Закон ассоциативности
(A+B)+C=A+(B+C)
(A ∙ B) ∙ C= A ∙(B ∙ C)

Распределительный закон
Закон дистрибутивности
(A+B)∙C=(A∙C)+(B∙C)
(A∙B)+C=(A+C)∙(B+C)

Закон инверсии
Формулы де Моргана

Формулы склеивания
(закон исключения)

Формулы поглощения

1. Является ли данная функция тождественно-истинной?
Способы решения:
Упрощение функции
Построение таблицы истинности

1 способ

1
2
3
4
5
2 способ

2. Следующие два высказывания истинны:
«неверно, что если магазин А организует распродажу, то магазин С тоже»;
«из двух магазинов В и С организует распродажу только один».
Какие магазины организуют распродажу?

«Если магазин А организует распродажу, то магазин С тоже»
A→C
«Неверно, что если магазин А организует распродажу, то магазин С тоже»
Из условия известно, что это высказывание истинно. Следовательно:

«Из двух магазинов В и С организует распродажу только один»

Это возможно только в одном случае, когда A=1, B=1, С=0.
То есть, магазины A и B проводят распродажу, а магазин С – нет.

3. На олимпиаде по информатике студенты A, B, C и D заняли первые четыре места. Когда их спросили о распределении мест, они дали три ответа: D – первый или B – второй; C – первый или A – четвертый; D – второй или B – третий. Как распределились места, если в каждом ответе только одно утверждение истинно?

D – первый или B – второй: D1+B2=1
C – первый или A – четвертый: C1+A4=1
D – второй или B – третий: D2+B3=1
(D1+B2)(C1+A4)(D2+B3)=1
(D1C1+B2C1+D1A4+B2A4)(D2+B3)=1
B2C1D2+D1A4D2+B2A4D2+B2C1B3+D1A4B3+B2A4B3=1
D1A4B3=1
Следовательно, D – первый, С – второй,
B – третий, A – четвертый.

3. Сформулируйте на естественном языке отрицание следующего высказывания:
"Виктор пойдет на рыбалку только при солнечной погоде, если не будет жарко".

«Виктор пойдет на рыбалку» - A
«Будет солнечная погода» - B
«Будет жарко» - C
Перефразируем высказывание:
«Если будет солнечная погода
и не будет жарко, то Виктор пойдет на рыбалку».
Тогда исходное высказывание имеет вид:

Будет солнечная погода и нежарко, а Виктор не пойдет на рыбалку.

Дизъюнктивно-нормальная форма
ДНФ — является логической суммой элементарных конъюнкций.
Совершенная ДНФ – логическая сумма элементарных конъюнкций, в каждой из которых присутствуют все переменные данной функции.

Конъюнктивно-нормальная форма
КНФ — является логическим произведением элементарных дизъюнкций.
Совершенная КНФ – логическое произведение элементарных дизъюнкций, в каждой из которых присутствуют все переменные данной функции.

Табличный способ приведения к СДНФ
Составляем таблицу истинности данной функции.
Рассматриваем только те строки таблицы, в которых функция принимает значение 1.
Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем аргумент, принимающий значение 0, входит в нее с отрицанием; значение 1 – без отрицания.
Наконец, образуем дизъюнкцию всех полученных конъюнкций.

Табличный способ приведения к СКНФ
Составляем таблицу истинности данной функции.
Рассматриваем только те строки таблицы, в которых функция принимает значение 0.
Каждой такой строке соответствует дизъюнкция всех аргументов (без повторений). Причем аргумент, принимающий значение 0, входит в нее без отрицания; значение 1 – с отрицанием.
Наконец, образуем конъюнкцию всех полученных дизъюнкций.

Если условится из двух форм, СДНФ и СКНФ, отдавать предпочтение той, которая содержит меньше букв, то
СДНФ предпочтительней, если в столбце значений функции таблицы истинности меньше единиц;
СКНФ – если в этом столбце меньше нулей.

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

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

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

Теперь по таблице истинности построим дизъюнктивно-нормальную форму.
Отберем те строки в таблице истинности, которые в результате дают единицу.
Для каждой строки строится конъюнкция всех переменных.
Если переменная в этой строке равна нулю, то она берется с отрицанием, если единице – без отрицания.
Затем соединим все полученные конъюнкции операциями дизъюнкции.

Стрелка Пирса (символ Лукашевича)
логическая операция с двумя переменными, соответствует обороту речи «ни…, ни…», обозначается следующим образом:
Выражение истинно в том и только в том случае, когда оба высказывания A и B ложны.

Стрелка Пирса (символ Лукашевича)

Штрих Шеффера
логическая операция с двумя переменными, соответствует обороту речи «не… или не…», обозначается следующим образом
Выражение A|B ложно в том и только в том случае, когда оба высказывания A и B истинны.

Штрих Шеффера

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

A
B
C
&
&
&
&
&
&
¬A
¬B
¬C
¬(A∙B∙¬C)
¬(A∙¬B)
¬((¬(A∙B∙¬C))∙(¬(A∙¬B)))

5. После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них – математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью:
Иван живет не в Минске.
Андрей – не в Витебске.
Житель Минска преподает не математику.
Андрей преподает не физику.
Повезло только жителю Витебска: он преподает любимую им химию.
Можно ли по этим данным определить, кто где живет и что преподает?

Алгоритм решения задач на приведение множеств во взаимно-однозначное соответствие
Строится пространственная система координат XYZ, на осях проставляются названия множеств и элементы этих множеств.
Читается условие задачи. Если пара элементов в двух множествах находится в соответствии, то точка, лежащая на пересечении соответствующих прямых становится центром темного кружка, в противном случае – белого кружка.
Применяется правило экстраполяции.
Применяется правило проектирования.
Повторять шаги 3)-4) пока это возможно.
Если в сложившейся ситуации возможности экстраполяции и проектирования исчерпаны, а задача не решена, то делается допущение о цвете фигуры в какой-либо свободной вершине сетки. В случае противоречия допущение отклоняется цвет фигуры в данной точке меняется на противоположный.

Правила экстраполяции в плоскости
«Темная» экстраполяция. Если на горизонтали (вертикали) все фигуры, кроме одной, светлы, то свободная занимается темной фигурой.
«Светлая» экстраполяция. Если на горизонтали (вертикали) имеется «темная» фигура, то все фигуры на ней – светлые.
Множественная экстраполяция. Если две (n) параллели в плоскости одинаково светло раскрашены везде за исключением двух (n) неокрашенных вершин, то на двух (n) параллелях другого направления, проходящих через эти вершины вне данных прямых вставляются светлые фигуры.

Правило множественного проектирования
«Темная» фигура в своей плоскости проектируется на координатные оси. Прямые, проведенные через проекции в двух других плоскостях, раскрашиваются одинаково.

Б
А
И
М
Х
Ф
М
В
Х
Имена
Предмет
Город