Учебное пособие для студентов заочного отделения
По учебной дисциплине
«Элементы математической логики»
специальности СПО 09.02.04 «Информационные системы (по отраслям»)
базовый уровень подготовки
09.02.03 «Программирование в компьютерных системах»
Разработала: Пучкова О.В., преподаватель ВКК
Математическая логика
Логические представления – это описание исследуемого процесса в виде совокупности сложных высказываний, составленных из простых высказываний и логических связок между ними, с использованием законов математической логики.
В математической логике изучают:
Способы формального представления высказываний;
Построение новых высказываний через имеющиеся с помощью логических преобразований;
Способы и методы установления истинности или ложности высказываний.
Логика высказываний. Основные понятия.
Высказывание – это повествовательное предложение о котором есть смысл говорить, ложно оно или истинно.
Например: «2+2=4»;
«Регистрация фирмы требует устава»;
«Рубль – Российская валюта».
Высказывание называется простым, если оно не содержит логических связок.
Высказывание называется сложным, если оно состоит из простых высказываний и логических связок между ними.
Основные логические операции
Конъюнкцией на высказываниях А и В называется высказывание истинное, если оба высказывания истинны, во всех остальных случаях – ложно.
Обозначение: А ∧ В; А · В; «А и В»; А & В.
Дизъюнкцией называется высказывание ложное, если оба высказывания ложны и истинное во всех других случаях.
Обозначение: А V В; «А или В»; А+В.
Отрицанием (инверсией) называется высказывание ложное, если само высказывание истинно, или истинное, если само высказывание ложное.
Обозначение: Ā; «не А»; ך А.
Импликацией (логическим следствием) двух высказываний называется высказывание ложное, если первое высказывание истинное, а второе ложное, во всех других случаях – истинно.
Обозначение: А→В; «если А, то В»; «из А следует В».
Эквивалентностью называется высказывание истинное, если оба высказывания имеют одинаковую истинность.
Обозначение: А↔В; А~В; «А тогда и только тогда, когда В».
Неравнозначностью (разделительное «или») называется высказывание истинное, если истинность высказываний не совпадает, и ложное в противном случае.
Обозначение: А ∆ В; «либо А, либо В».
Выражение называется логической формулой, если:
Любая переменная, обозначающая высказывание – формула;
Если А и В формулы, то (АΛВ),(АVВ),Ā,(А→В),(А↔В),(А~В),(А∆В) – формулы;
Других формул нет.
Упражнения:
Представить логической формулой следующие высказывания:
«Сегодня понедельник или вторник.»
«Идет дождь или снег.»
«Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые.»
«Что в лоб, что по лбу.»
«Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в плохом настроении или с головной болью.»
Алгебра логики. Многочлен Жигалкина.
Алгебра логики изучает строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Формулы алгебры логики – это логические выражения, состоящие из букв, знаков логических операций и скобок.
Буквы означают двоичные переменные, которые принимают только два значения истина или ложь.
Каждая формула задает логическую функцию от логических переменных, которая сама может принимать только значения истина или ложь.
Пусть В={0;1} – бинарное множество, где 1- истина, 0 – ложь.
Алгебра логики – это множество В со всеми возможными логическими операциями на нем.
Любую логическую функцию (многочлен Жигалкина) можно задать таблицей истинности, в левой части которой вписаны все возможные наборы ее аргументов, а правая часть представляет столбец значений функции, соответствующих этим наборам.
Число всех возможных наборов значений функции равно 2n.
Множество всех логических функций одной переменной:
| х | φ0 | φ1 | φ2 | φ3 |
| Нуле вая константа | х | ךх | Единичная константа |
Стандартный метод установления эквивалентности двух формул:
- По каждой формуле построить таблицу истинности;
- Полученные таблицы сравнить по каждому набору значений переменных.
Пример 1.
Доказать эквивалентность формулы: х1| х2~ х1Λ х2
| х1х2 | х1| х2 | х1Λ х2 | х1Λ х2 |
| 0 0 | |||
| 0 1 | |||
| 1 0 | |||
| 1 1 |
Пример 2. Доказать формулу де Моргана:
х1V х2~ х1Λ х2
| х1 х2 | х1Vх2 | х1Vх2 | х1 | х2 | х1Λх2 |
| 0 0 | |||||
| 0 1 | |||||
| 1 0 | |||||
| 1 1 |
Пример3. Доказать самостоятельно:
х 1 Λ х2 ~ х1 V х2
Пример4. Составить таблицу истинности функции трех переменных:
f(х1,х2,х3)=(х1 V х2)→(х1 Λ х3)
| х1 х2 х3 | х1 | х1V х2 | х1Λх3 | (х1V х2)→(х1Λх3) |
| 0 0 0 | ||||
| 0 0 1 | ||||
| 0 1 0 | ||||
| 0 1 1 | ||||
| 1 0 0 | ||||
| 1 0 1 | ||||
| 1 1 0 | ||||
| 1 1 1 |
Эквивалентные преобразования
Корректность преобразований обеспечивают:
Правило подстановки формулы F вместо переменной x.
Правило применяется к эквивалентным соотношениям для получения новых эквивалентных соотношений.
2. Правило замены подформул. Если какая-либо формула F, содержит F1 в качестве подформулы, то замена F1 на эквивалентную F2 не изменит формулы.
Эквивалентные преобразования – преобразования, использующие правила замены и эквивалентные соотношения.
1. Ассоциативность конъюнкции и дизъюнкции:
а) х1∧(х2∧х3)=(х1∧х2)∧х3=х1 ∧х2 ∧х3
б) х1∨(х2∨х3)=(х1∨х2)∨х3 =х1∨х2 ∨х3
2. Коммутативность дизъюнкции и конъюнкции:
а) х1∨х2 = х2∨х1 б) х1∧х2 =х2∧х1
3. Дистрибутивность конъюнкции относительно дизъюнкции:
х1∧(х2∨х3) =х1∧х2∨х1∧х3
4. Дистрибутивность дизъюнкции относительно конъюнкции:
х1∨(х2∧х3) =(х1∨х2)∧(х1∨х3)
5. Идемпотентность:
а) х∧х = х б) х∨х = х
6. Закон двойного отрицания:
х = х
7. Свойства констант:
а) х∧1 = х в) х∨1 = 1 д) 0 = 1
б) х∧0 = 0 г) х∨0 = х е) 1 = 0
8. Правила де Моргана:
а) х1∧ х2 = х1∨ х2 б) х1∨ х2 = х1 ∧ х2
9. Закон противоречия:
х∧ х = 0
10. Закон исключенного третьего:
х∨ х = 1
Упражнения:. Упростить формулу:
1. F(x,y,z)=x V x z V x y z V y z;
2. F(x,y,z)=x (y V z)(x V y V z).
3. F(x,y,z)=xy V xz V y z V yz V xy