ЕСЛИ-ТО Операция, выражаемая связками "если..., то", "из... следует", называется импликацией (лат. implico тесно связаны) и обозначается знаком. A B Высказывание А B ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: "данный четырёхугольник квадрат" (А) и "около данного четырёхугольника можно описать окружность" (В). Рассмотрим составное высказывание AB, понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание истинно: А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность; А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника); A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность. Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

A (данный четырехугольник –квадрат) B (около данного четырехугольника можно описать окружность) AB (Если данный четырехугольник – квадрат, то около него можно описать окружность)

ABABAB

ЭКВИВАЛЕНТНО (РАВНОСИЛЬНО) Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно...", называется эквивалентностью или двойной импликацией и обозначается знаком или ~. Высказывание истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывания: "24 делится на 6 тогда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а высказывания: "24 делится на 6 тогда и только тогда, когда 24 делится на 5", "21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

ABABAB

С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой. В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) C. Такая же формула соответствует высказыванию "если Игорь знает английский или японский язык, то он получит место переводчика". Как показывает анализ формулы (A v B) C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях значение "ложь"

A (Я куплю яблоки) B (Я куплю абрикосы) C (Я сварю компот ) A V BC (Если я куплю я блоки или абрикосы, то я сварю компот)

Сложное высказывание Составляющие простые высказывания Формула сложного высказывания F - Идет дождь, а у меня нет зонта А - идет дождь В – у меня есть зонт F = А В

Сложное высказываниеСоставляющие простые высказывания Формула сложного высказывания F – Идет направо – песнь заводит, налево – сказку говорит A - идет направо B – идет налево C – песнь заводит D – сказку говорит F=(AC) V (BD)

Сложное высказываниеСоставляющие простые высказывания Формула сложного высказывания F – Ваш приезд не является ни необходимым, ни желательным A – Ваш приезд необходимB – Ваш приезд желателен F = A B

F= (A B) (C D) A -Человек в детстве давал нервам властвовать над собой B - Человек в юности давал нервам властвовать над собой C – нервы привыкнут раздражаться D - нервы будут послушны F - Если человек в детстве и юности не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послушны. (К.Д. Ушинский)

F = (B C) A A – Некто является врачом B - Больной поговорил с врачом C – Больному стало легче F - Если больному после разговора с врачом не стало легче, то это не врач (В.М. Бехтерев)

Если сердце молчит, отказывает и память./Авессалом Подводный/ Если есть у тебя нечто лучшее, предложи, если ж нет - покоряйся. /Гораций/ Что мыслимо - то возможно, что возможно - то мыслимо. /Г. Лейбниц Знать много языков - значит иметь много ключей к одному замку. /Ф. Вольтер/ Я служу публике, но не поклоняюсь ей. /Б. Шоу/ Кто мудр, тот и добр. /Сократ/

Построение таблицы истинности логической функции, содержащей более одной логической связки Удобной формой записи при нахождении значений функции является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул. Здесь необходимо помнить, что существует приоритет логических операций: действия в скобках, отрицание ( - ), конъюнкция (&), дизъюнкция (V), импликация (=>), эквиваленция.( ) Пример. Построить таблицу истинности для логической функции y= (AVB) v A&C

Построение таблицы истинности логической функции, содержащей более одной логической связки Удобной формой записи при нахождении значений функции является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул. Здесь необходимо помнить, что существует приоритет логических операций: действия в скобках, отрицание ( - ), конъюнкция (&), дизъюнкция (V), импликация (=>), эквиваленция.( ) Пример. Построить таблицу истинности для логической функции y= (AVB) v A&C

Построение таблицы истинности логической функции, содержащей более одной логической связки Удобной формой записи при нахождении значений функции является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул. Здесь необходимо помнить, что существует приоритет логических операций: действия в скобках, отрицание ( - ), конъюнкция (&), дизъюнкция (V), импликация (=>), эквиваленция.( ) Пример. Построить таблицу истинности для логической функции y= (AVB) &C

Итак, нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность. Импликацию можно выразить через дизъюнкцию и отрицание: А В =A v В. Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию: А В = (A v В) (B v A) Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

ABCAVB F=AVB&C

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции дизъюнкция ("или") и в последнюю очередь импликация.

Алгебра логики строится на основе следующих аксиом: 1. Переменная может принимать лишь одно из двух возможных значений: A = 0, если A 1; A = 1, если A = 1; 1 = v 0 = 0; 1 v 1 = 1; 1 v 0 = 0 v 1 = & 0 = 0; 1 & 1 = 1; 1 & 0 = 0 & 1 = 0

1.Закон тождества Всякое высказывание тождественно самому себе: A = A 2.Закон непротиворечия Высказывание не может быть одновременно истинным и ложным Если высказывание А истинно, то его отрицание должно быть ложно A · A = 0 3.Закон исключенного третьего Высказывание может быть либо истинным, либо ложным, третьего не дано А v А = 1 4.Закон двойного отрицания Если дважды отрицать одно и то же высказывание, то получим исходное высказывание А = А

5. Закон нулевого множества: 0 v А = А; 0 & А = 0; 0 & А 1 & А 2 &... & А n &... = 0 6. Закон универсального множества: 1 & А = А; 1 v А = 1; 1 v А 1 v А 2 v... v А n v... = 1 7. Закон повторения: А & А = А; А v А = А.

8. Ассоциативный (сочетательный) закон: А & (B & C) = (A & B) & C = A & B & C; A v (B v C) = (A v B) v C = A v B v C 9. Дистрибутивный (распределительный) закон: A & (B v C) = A & B v A & C; A v B & C = (A v B) & (A v C)

10. Законы поглощения: A & (A v B) = A; A v A & B = A 11. Законы склеивания: A & B v A & B = A; (A v B) & (A v B) = A

13. Закон де Моргана (A v B) = A & B (A & B) = A v B

Как упростить логическую формулу? Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики. Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул: 1) законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами; 2) (применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

3) (повторяется второй сомножитель, затем комбинируются два первых и два последних сомножителя и используется закон склеивания 4) (вводится вспомогательный логический сомножитель ( ); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);

5) (сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания); 6) (выносятся за скобки общие множители; применяется правило операций с константами);

7) (к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания); 8) (общий множитель x выносится за скобки, комбинируются слагаемые в скобках первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);

9) (используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);

10) (используются правило де Моргана, закон двойного отрицания и закон поглощения).

Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом