Логика и алгоритмы. Теоретический материал

1.

Теоретический материал
Логика и алгоритмы
Доцент кафедры АЭМИС
к.т.н. Кечкина Наталия Игоревна

2.

Основные определения и понятия
Логическое
высказывание
–
это
повествовательное
предложение, относительно которого можно однозначно
сказать, истинно оно (1) или ложно (0).
Алгебра логики (булева алгебра) — это математический аппарат,
с помощью которого записывают, вычисляют, упрощают и
преобразуют логические высказывания.
Логическое выражение — это символическая запись
высказывания,
которая
может
содержать
логические
переменные и знаки логических операций.
Логическая функция — это правило преобразования входных
логических значений в выходные. Логическая функция задаётся
таблицей истинности.
Выражения:
A
A+A B
A (A+B)
A
0
0
1
1
B
0
1
0
1
F
0
0
1
1
функция
2

3.

Базовые логические операции
Операция НЕ (инверсия)
Если высказывание A истинно, то «не А» ложно, и наоборот.
А
не А
0
1
1
0
также A , A ,
Python not
таблица
истинности
операции НЕ
3

4.

Базовые логические операции
Операция И (логическое умножение, конъюнкция)
Высказывание «A и B» истинно тогда и только тогда, когда А и B
истинны одновременно.
0
1
2
3
A
B
АиB
0
0
1
1
0
1
0
1
0
0
0
1
также: A·B, A B,
в Python and
4

5.

Базовые логические операции
Операция ИЛИ (логическое сложение, дизъюнкция)
Высказывание «A или B» истинно тогда, когда истинно А или B, или
оба вместе.
A
B
А или B
0
0
1
1
0
1
0
1
0
1
1
1
также: A+B, A B,
в Python or
5

6.

Логические операции
Операция «исключающее ИЛИ»
Высказывание «A B» истинно тогда, когда истинно А или B, но не
оба одновременно (то есть A B).
A B A B A B
A
0
0
1
1
B
0
1
0
1
A B
0
0
1
0
A B A B A B А B
0
1
0
0
0
1
1
0
0
1
1
0
6

7.

Логические операции
Импликация («если …, то …»)
Высказывание «A B» истинно, если не исключено, что из А
следует B.
A B A B
A
0
0
1
1
B
0
1
0
1
А B
1
1
0
1
7

8.

Логические операции
Эквиваленция («тогда и только тогда, …»)
Высказывание «A B» истинно тогда и только тогда, когда А и B
равны.
A B A B A B A B
A
0
0
1
1
B
0
1
0
1
А B
1
0
0
1
8

9.

Логические операции
Штрих Шеффера, «И-НЕ»
A | B A B
A
0
0
1
1
B
0
1
0
1
А|B
1
1
1
0
Стрелка Пирса, «ИЛИ-НЕ»
A B A B
A
0
0
1
1
B
0
1
0
1
А↓B
1
0
0
0
9

10.

Вычисление логических выражений
Порядок вычислений:
•скобки
• НЕ
•И
• ИЛИ, исключающее ИЛИ
• импликация
• эквиваленция
10

11.

Законы алгебры логики
название
для И
для ИЛИ
A A
двойного отрицания
A A 0
A A 1
операции с
константами
A 0 0, A 1 A
A 0 A, A 1 1
повторения
A A A
A A A
исключения третьего
поглощения
переместительный
A ( A B) A
A A B A
A B B A
A B B A
сочетательный
A (B C) ( A B) C A (B C) ( A B) C
распределительный
A B C ( A B) ( A C)
A (B C) A B A C
законы де Моргана
A B A B
A B A B
11

12.

Упрощение логических выражений
Шаг 1. Заменить операции на их выражения
через И, ИЛИ и НЕ:
A B A B A B
A B A B
A B A B A B
Шаг 2. Раскрыть инверсию сложных выражений по
формулам де Моргана:
A B A B,
A B A B
Шаг 3. Используя законы логики, упростить
выражение.
12

13.

Задания
№ 10403
Логическая функция F задаётся выражением:
(¬x ∧ y) ∨ (y ∧ z).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий
все наборы аргументов, при которых функция F истинна.
Определите, какому столбцу таблицы истинности функции F соответствует
каждая из переменных x, y, z.
В ответе напишите буквы x, y, z в том порядке, в котором идут
соответствующие им столбцы (сначала буква, соответствующая первому
столбцу, затем буква, соответствующая второму столбцу, и т. д.) Буквы в ответе
пишите подряд, никаких разделителей между буквами ставить не нужно.
13

14.

Задания
№ 10403
Вариант решения 1
(¬x ∧ y) ∨ (y ∧ z)=1
(¬x ∧ y)=1
(¬x ∧ y)=1
(¬x ∧ y)=0
(y ∧ z)=1
(y ∧ z)=0
(y ∧ z)=1
Отметим, что y встречается и в первой, и во второй скобке. Пусть y – перем. 2.
Предположим, что z – перем. 1. Функция должна быть = 1, но при данном
наборе переменных значение – 0. Значит наше предположения неверно.
Рассмотрим вариант x – перем. 1.
Ответ: xyz
14

15.

Задания
№ 10403
Вариант решения 2
Таблица истинности выражения
x
0
0
0
1
1
1
1
0
y
0
0
1
1
0
1
0
1
z
0
1
1
1
0
0
1
0
не x
1
1
1
0
0
0
0
1
не x & y y & z
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
(¬x ∧ y) ∨ (y ∧ z)
0
0
1
1
0
0
0
1
15

16.

Задания
№ 10403
Вариант решения 3
Таблица Excel
Вариант решения 4
Python
16

17.

Задания
№ 15124
Логическая функция F задаётся выражением
(x ≡ y ) ∨ ((y ∨ z) → x).
Дан частично заполненный фрагмент, содержащий неповторяющиеся
строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из
переменных x, y, z.
В ответе напишите буквы x, y, z в том порядке, в котором идут
соответствующие им столбцы (сначала — буква, соответствующая первому
столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в
ответе пишите подряд, никаких разделителей между буквами ставить не
нужно.
Ответ:
17

18.

Задания
№ 15124
Вариант решения Python
== эквивалентность
<= импликация
Ответ: xzy
18