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

1.

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

2.

логика
(мышленийын законжо да формыжо-влак нерген наука).
Логикым тунемаш изучать логику.

3.

Логическое выражение
(логическая формула)
Логическая формула может включать
логические константы (0 или 1),
логические переменные, знаки логических
операций
Пример логического выражения:
(A & B) → (¬A & C)
Простейшее логическое выражение – это одна
логическая константа или одна логическая
переменная

4.

Старшинство логических
операций
1) Скобки
2) Отрицание
3) Конъюнкция
4) Дизъюнкция и исключающее ИЛИ
5) Импликация и эквивалентность

5.

Логическая функция
Логической функцией называется зависимость
одной переменной логической величины (значения
функции) от значений других независимых
логических величин – аргументов
Пример логической функции:
F (A, B, C) = (A & B) → (¬A & C)

6.

Таблица истинности – однозначное
отображение логической функции
F (A, B, C) = (A & B) → (¬A & C)
A
B
C
¬A
A&B
¬A&C
F
0
0
0
1
0
0
1
0
0
1
1
0
1
1
0
1
0
1
0
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
0
0
1
0
0
1
1
1
0
1
0
0

7.

I) Постройте таблицы истинности
1) ВПР 8 класс, заполните таблицу
истинности выражения.
а) A \/ (A /\ B);
б) A /\ (A \/ B); - домашнее задание
2) ВПР 8 класс, заполните таблицу истинности
выражения.
а) ¬(A \/ B) \/ B /\ ¬ C;
б) ¬(A \/ B) \/ A /\ ¬ C; - домашнее задание

8.

II) Постройте таблицы истинности и
определите равносильные выражения
3)
а) Укажите, какое логическое выражение равносильно
выражению ¬(A \/ ¬ B \/ C).
1) ¬A \/ B \/ ¬C
2) A /\ ¬B /\ C
3) ¬A \/ ¬B \/ ¬C
4) ¬A /\ B /\ ¬C
Ответ: логическое выражение ¬(A \/ ¬ B \/ C) равносильно выражению
б) домашнее задание Укажите, какое логическое
выражение равносильно выражению A /\ ¬ (¬B \/ C).
1)
¬A \/ ¬B \/ ¬C
3) A /\ B /\ ¬C
2)
A /\ ¬B /\ ¬C
4) A /\ ¬B /\ C
Ответ: логическое выражение A /\ ¬ (¬B \/ C) равносильно выражению

9.

III) Постройте таблицы истинности и
определите равносильные выражения
4)
а) Символом F обозначено одно из указанных ниже логических
выражений от трех аргументов X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
XYZ
F
1 1 1
1
1 1 0
1
1 0 1
1
Какое выражение соответствует F?
1) X \/ ¬Y \/ Z 2) X /\ Y /\ Z
3) X /\ Y /\ ¬Z 4) ¬X \/ Y \/ ¬Z

10.

III) Постройте таблицы истинности и
определите равносильные выражения
4) домашнее задание
б) Символом F обозначено одно из указанных ниже логических
выражений от трех аргументов X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
XYZ
F
1 0 1
1
0 1 0
1
1 1 0
0
Какое выражение соответствует F?
1) ¬X /\ Y \/ ¬Z
2) ¬X \/ ¬Y /\ Z
3) X \/ Y \/ Z
4) ¬X /\ ¬Y /\ Z

11.

IV) Постройте таблицы истинности и
определите равносильные выражения
5)
а) Для какого из приведённых чисел истинно высказывание:
НЕ (Первая цифра чётная) И (Последняя цифра нечётная)?
1) 1234
2) 6843
3) 3561
4) 4562
A = «Первая цифра чётная»
B = «Последняя цифра нечётная»
Представим высказывание из условия задачи в виде логического
выражения: ¬A/\B. Построим таблицу истинности:
Ответ:

12.

IV) Постройте таблицы истинности и
определите равносильные выражения
5)
б) домашнее задание
Для какого из приведённых имён истинно высказывание:
НЕ(Первая буква гласная) И НЕ(Последняя буква
согласная)?
1) Емеля
2) Иван
3) Михаил
4) Никита
A = «Первая буква гласная»
B = «Последняя буква согласная»
Построим логическое выражение: ¬A /\ ¬B. Строим таблицу
истинности:
Ответ:

13.

Проблема разрешимости
Все формулы алгебры логики делятся на три
класса:
Формула называется тождественно-истинной
(тавтологией), если для любых наборов переменных она
принимает значение И.
Формула называется тождественно-ложной, если для
любых наборов переменных она принимает значение Л.
Формула называется выполнимой, если для некоторых
наборов переменных она принимает значение И.

14.

Проблема разрешимости
Пример 1:
Быть или не быть — вот в чем вопрос!
/У.Шекспир/

15.

Проблема разрешимости
тл
Пример 2: к какому классу относится данная формула
¬(A \/ B) & (A & ¬B)

16.

Проблема разрешимости
ти
Пример 3: к какому классу относится данная формула
Y→(X→(Y/\X))

17.

Проблема разрешимости
вып
Пример 4: к какому классу относится данная формула
(A \/ B) /\ (A & ¬B)

18.

Домашнее задание
1) Параграф 19 (Л.Л.Босова)
2) Учить таблицы истинности логических
операций
3) Подготовиться к самостоятельной работе
по теме «Таблицы истинности»