Лекция по "Логике"

 

 

 

A	неА
1	1
1	0

Логическое отрицание: ИНВЕРСИЯ - если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО

 

  

 

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

Логическое следование:  ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом  "следовательно"  и  выражается словами ЕСЛИ … , ТО …

 

  

 

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения  двух простых логических выражений  А и В. Результатом ЭКВИВАЛЕНТНОСТИ  является новое логическое выражение, которое будет истинным тогда  и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности"

 

 Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия 

2. конъюнкция

3. дизъюнкция

4. импликация

5. эквивалентность 

Для изменения указанного порядка выполнения операций используются скобки.  

Построение таблиц истинности для  сложных выражений:

Количество строк = 2n + две строки для заголовка  (n - количество простых высказываний)

Количество  столбцов = количество переменных + количество логических операций

При построении таблицы надо учитывать  все возможные сочетания логических значений 0 и 1 исходных выражений. Затем  – определить порядок действий и  составить таблицу с учетом таблиц истинности основных логических операций.

ПРИМЕР:  составить таблицу истинности сложного логического выражения D = неA & ( B+C )

А,В, С - три простых высказывания, поэтому :

количество строк  = 23 +2 = 10 (n=3, т.к. на входе три элеманта А, В, С)

количество столбцов :  1) А

2) В

3) С

4) не A  это инверсия А  (обозначим Е)

5) B + C это операция дизъюнкции (обозначим F)

6) D = неA & ( B+C ), т.е. D = E &  F это операция конъюнкции

1	2	3	4	5	6
А	В	С	E = не А  (не 1)	F = В+С (2+3)	D = E&F (4*5)
1	1	1	0	1	0
1	1	0	0	1	0
1	o	1	0	1	0
1	o	0	0	0	0
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	1	1
0	0	0	1	0	0

 

 

Логические формулы. Законы алгебры логики

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон	Для   ИЛИ	Для   И
Переместительный
Сочетательный
Распределительный
Правила де Моргана
Идемпотенции
Поглощения
Склеивания
Операция переменной с ее инверсией
Операция с константами
Двойного отрицания

 

Упрощение  логической формулы

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении  логических формул:

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

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

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

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

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

6)   (выносятся за скобки общие множители; применяется правило операций с константами);

7)   (к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);

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

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

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

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

Методы решения логических задач

Исходными данными в логических задачах являются высказывания. Эти  высказывания и взаимосвязи между  ними бывают так сложны, что разобраться в них без использования специальных методов достаточно трудно. Многие логические задачи связаны с рассмотрением нескольких конечных множеств и связей между их элементами. Для решения таких задач зачастую прибегают к помощи таблиц или графов, при этом успешность решения во многом зависит от удачно выбранной структуры таблицы или графа. Аппарат же алгебры логики позволяет построить формальный универсальный способ решения логических задач.

Формальный способ решения логических задач

1.  Выделить из условия задачи  элементарные (простые) высказывания  и обозначить их буквами.

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

3.  Составить единое логическое выражение для всех требований задачи.

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

5.  Выбрать решение — набор  значений простых высказываний, при котором построенное логическое выражение является истинным.

6.  Проверить,   удовлетворяет   ли   полученное   решение  условию задачи.