Основы математической логики. Тема 3.1

1.

1.3 Основы математической
логики
Ст. преподаватель кафедры ИКТ
Андреева Н.Б.

2.

Вопросы:
Основы математической логики

3.

Основы математической логики
1.3 Основы математической логики
Основные понятия математической логики
Аппарат алгебры логики (булевой алгебры) создан в 1854 г. английским
математиком Дж. Булем.
Алгебра логики – раздел математики, изучающий высказывания,
рассматриваемые со стороны их логических значений (истинности или
ложности) и логических операций над ними.
Аппарат булевой алгебры, как и любая другая формальная математическая
система, состоит из трех множеств: элементов, операций над ними и
аксиом.
Высказывание – некоторое предложение, в отношении которого можно
однозначно сказать, истинно оно или ложно.
Элементы. Множество элементов булевой алгебры выбирается
бинарным
В = {0,1},
а сама алгебра называется бинарной, или переключательной.
Ее элементы называются константами, или логическими 0 и 1, которым в
ряде случаев соответствуют бинарные цифры, в других случаях – логические
значения, соответственно ложь (False) и истина (True).

4.

Для справки.
Джордж Буль (1815–1864) – английский математик и логик, по
праву считается отцом математической логики. Его именем назван
раздел математической логики – булевая алгебра.
Джордж Буль смог окончить только начальную школу для детей
бедняков, в других учебных заведениях он не учился: не позволило
тяжелое материальное положение его родителей. Он самоучка. В
совершенстве владел латынью, греческим, французским, немецким
и итальянским языками; зачитывался математическими журналами.
Этим отчасти и объясняется, что, не связанный традицией, он
пошел в науке собственным путем.
В 1848 г. Джордж Буль опубликовал статью по началам
математической логики «Математический анализ логики, или Опыт
исчисления дедуктивных умозаключений».
Дж. Буль в 1849 г. получил пост профессора математики Куинзколледжа в графстве Корк, несмотря на то, что даже не имел
университетского образования.
В 1854 г. появился главный его труд – «Исследование законов
мышления, на которых основаны математические теории логики и
вероятностей».
В ХХ столетии ученые объединили созданный Джорджем Булем
математический аппарат с двоичной системой счисления, заложив
тем самым основы для разработки ЭВМ.

5.

Основы математической логики
Базовые логические операции
Операция
Название операции
И (AND)
Логическое умножение –
конъюнкция
Логическое сложение –
ИЛИ
(OR)
дизъюнкция
НЕ (NOT) Логическое отрицание –
инверсия (дополнение)
Обозначение
операции
^
(амперсанд)
+
–
Выполняемая функция
Пересечение
высказываний
двух
Объединение
высказываний
Применяется
аргументу
двух
к
одному
•При выполнении операций применяются отношение эквивалентности
«=» и скобки «( )», которые определяют порядок выполнения
операций.
•Если скобок нет, то операции выполняются в следующей
последовательности: логическое отрицание, логическое умножение и
логическое сложение.

6.

Основы математической логики
Аксиомы (постулаты) алгебры логики.
При выполнении логических операций используются следующие аксиомы:
1. Дизъюнкция (логическое сложение) двух переменных равна 1, если хотя бы одна
из них равна 1, и равна 0, если обе переменные равны 0, т. е. результатом
операции ИЛИ является выражение, которое будет истинным тогда и только тогда,
когда истинно будет хотя бы одно из исходных выражений.
Формула функции логического сложения:
F A B
где F – составное высказывание,
A, B – аргументы (логические переменные, исходные высказывания).
Значение логической функции можно определить с помощью таблицы истинности
данной функции, которая показывает, какие значения принимает логическая
функция при всех возможных наборах ее аргументов:
A
B
F A B
0
0
0
0
1
1
1
0
1
1
1
1
Например,
• рассмотрим составное высказывание «2 x 2 = 4 или 3 x 3 = 10»: первое простое высказывание
истинно (А=1), а второе высказывание ложно (B=0), следовательно, логическая функция
принимает значение истина (F=1);
• рассмотрим другое высказывание «Знания или везение – залог сдачи экзаменов»: успешно
сдать экзамен может тот, кто все знает, или тот, кому повезло (например, вытянут единственный
выученный билет), или тот, кто все знает и при этом выбрал «хороший» билет.

7.

Основы математической логики
2. Конъюнкция (логическое умножение) двух переменных равна 0, если
хотя бы одна переменная равна 0 и равна 1, если обе переменные равны
1, т. е. результатом операции И является выражение, которое будет
истинным тогда и только тогда, когда истинны оба исходных выражения.
Формула функции логического умножения:
F A&B
где F – составное высказывание,
A, B – аргументы.
Значение логической функции можно определить с помощью таблицы
истинности данной функции, которая показывает, какие значения
принимает логическая функция при всех возможных наборах ее
аргументов:
A
0
0
1
1
F A&B
B
0
1
0
1
0
0
0
1
Например,
• рассмотрим составное высказывание «2 x 2 = 4 или 3 x 3 = 10»: первое простое высказывание
истинно (А=1), а второе высказывание ложно (B=0), следовательно, логическая функция
принимает значение ложь (F=0).
• рассмотрим другое высказывание «Терпение и труд все перетрут»: достижение цели возможно
только при одновременной истинности двух предпосылок – терпения и труда.

8.

Основы математической логики
3. Инверсия (логическое отрицание) одного значения переменной
совпадает с ее другим значением, т. е. результатом операции НЕ
является следующее: если исходное выражение истинно, то
результат его отрицания будет ложным; если исходное
выражение ложно, то результат его отрицания будет истинным.
Образуем высказывание:
F A
где F – логическое высказывание,
A – аргумент.
Истинность такого высказывания задается таблицей истинности
функции логического отрицания:
F A
A
0
1
1
0
Например,
• высказывание «Два умножить на два равно четырем» истинно (А=1), а
полученное из него в результате логического отрицания высказывание «Два
умножить на два не равно четырем» ложно (F=0).
• пусть существует высказывание «Пасмурная погода есть 0, солнечная погода
есть 1», тогда «НЕпасмурная погода – солнечная погода», а «НЕсолнечная погода –
пасмурная погода»

9.

Законы алгебры логики.
Рассмотрим основные законы алгебры
логики.
1. Законы однопарных элементов:
а) универсального множества:
x + 1 = 1;
х∙1 = х,
б) нулевого множества:
х + 0 = х;
х ∙ 0 = 0.

10.

2.
Законы отрицания:
а) двойного отрицания:
x x
б) дополнительности:
x x 1;
xx 0.
в) двойственности (де Моргана):
x1 x2 x1 x2 ;
x1 x2 x1 x2 .

11.

3.
Комбинационные законы:
а) тавтологии (идемпотенции): x x x;
x x x.
б) коммутативные:
x1 x2 x2 x1;
x1 x2 x2 x1.
в) ассоциативные (сочетательные): x1 x2 x3 x1 x2 x3 ;
x1 x2 x3 x1 x2 x3 .
г) дистрибутивные (распределительные): x1 x2 x3 x1 x2 x1 x3 ;
x1 x2 x3 x1 x2 x1 x3 .
д) закон абсорбции (поглощения):
е) склеивания:
x1 x2 x1 x2 x1;
x1 x2 x1 x2 x1.
x1 x1 x2 x1;
x1 x1 x2 x1.

12.

Упрощение (минимизация) логических выражений
Суперпозиция - операция замены одной функции другими.
Нормальной формой считают представление функций посредством
суперпозиций вспомогательных функций – минтермов и макстермов:
минтерм – функция, которая принимает 1 только при одном значении
аргументов и 0 – при других,
макстерм - функция, которая принимает 0 только при одном значении
аргументов и 1 – при другом.
Минтерм - инверсия макстерма.
Суперпозиция минтермов:
N 1
y x1 x2 ...xn y c , N 2
i 1
1
1 i
2n
Суперпозиция макстермов:
N 1
y x1 x2 ...xn yi Ci0
i 1

13.

Обычно запись функции осуществляется в виде:
СДНФ – совершенных дизъюнктивных нормальных форм,
СКНФ - совершенных конъюнктивных нормальных форм,
что часто является избыточной и ее можно сократить, т.е. упростить.
Под упрощением формулы, не содержащей операций импликации и
эквиваленции, понимают равносильное преобразование, приводящее к
формуле, которая
либо содержит по сравнению с исходной меньшее число операций
конъюнкции (дизъюнкции) и не содержит отрицаний
неэлементарных формул,
либо содержит меньшее число вхождений переменных.

14.

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

15.

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

16.

так, по закону дополнительности
y y 1 и затем x x 1

17.

распределительный закон
закон поглощения (общий
множитель yz – за скобку),
затем – закон дополнительности

18.

19.

Пример
Дано: функция F(a, b. с) равна «1» на наборах переменных с номерами 0, 1, 2, 3, 5.
№ a b
c
F(a,b,c)
Задание:
0
0 0
0
1
а) представить функцию F (а, b, с) в табличной форме;
1
0 0
1
1
2
б) перейти к аналитической форме задания функции (СДНФ);
0 1
0
1
3
0 1
1
1
в) минимизировать функцию с помощью законов алгебры логики.
4
1 0
0
0
Решение:
5
1 0
1
1
6
1 1
0
0
а) представляем функцию F (а, b, с) в табличной форме:
7
1
1
1
0

20.

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

21.

Логическое следование (импликация).
Логическое следование (импликация) образуется
соединением двух высказываний в одно с помощью
оборота речи «если ..., то ...».
Логическая операция импликации «если А, то Б»
обозначается А —> В и выражается с помощью
логической функции F, которая задается
соответствующей таблицей истинности
Составное высказывание, образованное с помощью
операции логического следования (импликации),
ложно тогда и только тогда, когда из истинной посылки
(первого высказывания) следует ложный вывод
(второе высказывание).
Если первое высказывание (посылка)
ложно, то вне зависимости от
истинности или ложности второго
высказывания (вывода) составное
высказывание истинно.
Это можно понимать таким образом,
что из неверной посылки может
следовать что угодно.

22.

Например,
высказывание «Если число делится на
10, то оно делится на 5» истинно, так
как истинны и первое высказывание
(посылка), и второе высказывание
(вывод),
высказывание «Если число делится на
10, то оно делится на 3» ложно, так как
из истинной посылки делается ложный
вывод.

23.

Логическое равенство (эквивалентность).
Логическое равенство (эквивалентность) образуется
соединением двух высказываний в одно с помощью
оборота речи «... тогда и только тогда, когда ...».
Логическая операция эквивалентности «А
эквивалентно В» обозначается
А~В
и выражается с помощью логической функции F,
которая задается соответствующей таблицей
истинности
Составное высказывание,
образованное с помощью
логической операции
эквивалентности, истинно
тогда и только тогда, когда оба
высказывания одновременно
либо ложны, либо истинны.

24.

Например,
два высказывания:
А – «Компьютер может производить вычисления»
и В = «Компьютер включен».
Составное высказывание, полученное с помощью операции
эквивалентности, истинно, когда оба высказывания либо
истинны, либо ложны:
«Компьютер может производить вычисления тогда и только
тогда, когда компьютер включен».
«Компьютер не может производить вычисления тогда и только
тогда, когда компьютер не включен».
Составное высказывание, полученное с помощью операции
эквивалентности, ложно, когда одно высказывание истинно, а
другое ложно:
«Компьютер может производить вычисления тогда и только
тогда, когда компьютер не включен».
«Компьютер не может производить вычисления тогда и только
тогда, когда компьютер включен».

25.

Основы математической логики
Приложения математической
логики
Впервые практическое применение булевой
алгебры было сделано К. Шенноном в 1938 г.
для анализа и разработки релейных
переключательных сетей:
упрощенно можно представить работу компьютера как
некоторого устройства, производящего обработку
двоичных сигналов, соответствующих 0 и 1.
Такую обработку в компьютере выполняют
логические элементы.
Логический элемент – это устройство,
выполняющее одну из основных логических
операций: И, ИЛИ, НЕ.

26.

К основным логическим элементам
вычислительных устройств относятся
электронные схемы, реализующие
операции:
И,
ИЛИ,
НЕ,
И- НЕ,
ИЛИ-НЕ
и др.

27.

Технически логический элемент реализуется в виде электрической
схемы, которая представляет собой соединение различных
деталей: диодов, транзисторов, резисторов, конденсаторов.
На вход логического элемента поступают электрические сигналы
высокого и низкого уровней напряжения (значения аргументов),
которые интерпретируются в зависимости от реализуемых функций
и на выход выдается один выходной сигнал (значение функции)
также либо высокого, либо низкого уровня. Эти уровни
соответствуют одному из состояний двоичной системы: 1 – 0;
ИСТИНА – ЛОЖЬ.
Из логических элементов составляются электронные логические
схемы. Тысячи микроскопических электронных переключателей в
кристалле интегральной схемы сгруппированы в системы,
выполняющие логические и арифметические операции над
двоичными числами.
Операции булевой алгебры часто встречаются и в программном
обеспечении вычислительных устройств, где они используются для
замены аппаратной логики на программную.

28.

Схема И
Реализует конъюнкцию
двух или более логических
(AB)
значений:
единица (1) на выходе
схемы будет тогда и только
тогда, когда на всех входах
будут единицы (1);
когда хотя бы на одном входе будет ноль (0),
на выходе также будет ноль (0).
Примечание – знак & («амперсэнд» - сокращенная запись
английского слова and) – конъюнкция.

29.

Схема ИЛИ
Реализует дизъюнкцию
двух или более логических
значений:
когда хотя бы
на одном входе схемы будет
единица (1), на её выходе также
будет единица (1).
(AVB)

30.

Схема НЕ (инвертор)
Реализует операцию
отрицания:
если на входе схемы
ноль (0), то на выходе
единица (1);
когда на входе единица (1),
то на выходе ноль (0).
(Ā)

31.

Схема И-НЕ
Состоит из элемента И
и инвертора и осуществляет
отрицание результата схемы И.
AB

32.

Схема ИЛИ-НЕ
Состоит из элемента ИЛИ
и инвертора и осуществляет
отрицание результата схемы ИЛИ.
A B

33.

Вопросы для самопроверки
1. Правильным результатом выполнения логической
операции дизъюнкции (ИЛИ) является…
1) ЛОЖЬ ИЛИ ИСТИНА = ИСТИНА +
2) ИСТИНА ИЛИ ЛОЖЬ = ЛОЖЬ
3) ИСТИНА ИЛИ ИСТИНА = ЛОЖЬ
4) ЛОЖЬ ИЛИ ЛОЖЬ = ИСТИНА
2 Результатом выполнения логической операции
будет ИСТИНА, если…
1) A – ИСТИНА, B – ЛОЖЬ, C – ИСТИНА +
2) A – ИСТИНА, B – ЛОЖЬ, C – ЛОЖЬ
3) A – ИСТИНА, B – ИСТИНА, C – ЛОЖЬ
4) A – ЛОЖЬ, B – ЛОЖЬ, C – ЛОЖЬ

34.

3. Определить результат выполнения логической
операции
A B C
если…
A – ИСТИНА, B – ИСТИНА, C – ЛОЖЬ
Решение:
Операции выполняются в следующей
последовательности:
логическое отрицание,
логическое умножение,
логическое сложение.
Если ложь – логический 0; истина – логическая 1, то
A B C 1 1 0 1 0 0 1 0 1
Ответ: ИСТИНА

35.

4. Определить значение логической
функции , если А = 1 B = 1:
F A B A 1 1 1 0 0 0 0
Ответ:
F A B A 0

36.

5. Логическому выражению
равносильно выражение …
Решение. Применим закон де Моргана к
составному высказыванию:
По закону двойного отрицания
Тогда
И в итоге получаем, что логическое выражение
является верным вариантом ответа.

37.

6. Логическая функция
принимает значение Ложь (0) при …?
Решение.
Порядок выполнения логических операций:
1)
2)
3)
4)
5)
Составим таблицу истинности логической функции
Из таблицы видно, что логическая функция F принимает значение 0 только
при

38.

6. На рисунке представлено условное
графическое изображение
логической схемы. Связь между
выходом z и входами х и у для
данной логической схемы
записывается в виде …
Решение. На рисунке представлено условное обозначение логической
схемы И-НЕ.
Схема И-НЕ является комбинацией элемента И и инвертора (НЕ). Она
осуществляет операцию отрицания результата схемы И.
Связь между выходом и входами x и y схемы записывается в виде
и читается как «инверсия x и y».

39.

Примечание:
Обозначение
соответствует операции, выполняемой логической схемой
ИЛИ-НЕ (читается как «инверсия X или Y»).
Условное графическое обозначение логической схемы,
выполняющей операцию ИЛИ-НЕ, представлено на рисунке.
Обозначение
соответствует операции, выполняемой логической схемой И
(читается как «X и Y»).
Условное графическое обозначение логической схемы,
выполняющей операцию И, представлено на рисунке.
Обозначение
соответствует операции, выполняемой логической схемой
ИЛИ (читается как «X или Y»).
Условное графическое обозначение логической схемы,
выполняющей операцию ИЛИ, представлено на рисунке.

40.

Задание 1. Выходная функция F приведенной логической схемы равна = 1 при следующей
комбинации входных сигналов:
A
B
1
&
C
1
F
(1100)
(1110)
(1000)
(0101)
D
Задание 2. Выходная функция F приведенной логической схемы равна = 1 при следующей
комбинации входных сигналов:
A
B
&
1
C
&
D
F
(1100)
(1110)
(1001)
(0100)

41.

Реализация логических функций на базовых логических элементах
Пример 1
Дано: логическая формула имеет следующий вид: F=(A˅B) ˄C ˅ ¬A
Задание: реализовать формулу в виде схемы на базовых логических элементах
НЕ, И, ИЛИ,
Решение: определим, какие логические элементы и сколько таких элементов
потребуется для вычерчивания схемы.
Ясно, что над значением А будет выполняться операция отрицание - для этого
необходим один элемент НЕ. Необходимы два элемента ИЛИ: в них будут
складываться значения А и B, а также значения и . Потребуется также один
элемент И для умножения суммы А и В на С.
Таким образом, схема будет иметь следующий вид:

42.

Пример 2