Основные понятия алгебры логики. Логические выражения и логические операции

(1815-1864)
основоположник математической логики
A↔B

помощью 0 и 1.
Задача – разработать оптимальные правила обработки таких

предметов, позволяющие отличать их друг от друга

(Пример: Прямоугольник - геометрическая

может быть получено новое суждение
(знание или вывод)

(Пример: любая теорема)

утверждается или отрицается)

(Пример: Париж – столица Франции)

отражает свойства и отношения реальных вещей
Высказывание не соответствует реальной действительности
Высказывание
Простое
Составное
Логическое

предмет.
У квадрата – 10 сторон и все разные.
Красиво!
В городе N

составных высказываний.
Основные понятия:
логическая переменная
логическая функция
логическая операция

латинская буква (А, Х, Y и т.д.).
Значением логической переменной могут

A – Сейчас идет дождь.
B – Форточка открыта.

собой с помощью логических операций.
Ее символическое обозначение –
F(A, B,..).

(элементарные)
Составные высказывания строятся из простых с помощью логических связок (операций)

A и B
A или не B
если A, то B
A тогда и только
тогда, когда B

Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.

(инверсия)
2.4. Логическое следование (импликация)
2.5. Логическое равенство (эквивалентность)

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

Таблица истинности логического выражения –
это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения для каждой комбинации.

между подмножествами, для наглядного представления. Изобретены Леонардом Эйлером.

с помощью союза «и».
Например: Сейчас идет дождь и открыта

Соответствует союзу И
Обозначение &, , , И.

Таблица истинности

A

B

А&В

Графическое представление

помощью союза «или».
Например: Сейчас идет дождь или форточка закрыта.
Составное высказывание

Соответствует союзу ИЛИ
Обозначение V, |, ИЛИ, +.

Таблица истинности

ложным и, наоборот.
Соответствует союзу НЕ
Обозначение Ā, ¬А
В языках программирования not
Таблица

A

Сейчас дождя нет

Сейчас дождь не идет

двух высказываний в одно с помощью оборота речи «если…, то…».
Импликация

Таблица истинности

помощью оборота речи «… тогда и только тогда, когда …».
Составное

Таблица истинности

Соответствует обороту тогда и только тогда, когда …
Обозначение А≡В, А~B

Например: Дождь идет тогда и только тогда, когда открыта форточка.

выразить через отрицание, дизъюнкцию и 
конъюнкцию: А    В = ( A v В) . (B

формулы на обычном языке.

А&В

Задачи 1

высказываний:

А = {Принтер – устройство вывода информации},
В =

5 букв  Четвёртая буква гласная?
Ответ: 3
Задачи 2

1  0

0

1  1

1  0

1 * 0

=

=

=

=

0 * 0

1 * 1

1 * 0

=

=

=

=

0

0

0

1

буква согласная?
1) Петр
2) Алексей
3) Наталья
4) Елена
Ответ: 3

 Четвёртая буква согласная  В слове 4 буквы?
1) Сергей
2)

Ответ: 4, 5

буква гласная?
1) короед
2) усач
3) скрипун
4) плоскоход
new
Ответ: 3

диаграмма изображает множество страниц, найденных по заданному запросу?
Ответ Г
A
В
Б
Г
Задачи 3

в порядке возрастания количества страниц, которые найдёт поисковый сервер по

страниц …

которую войдут логические переменные и знаки логических операций, то получится

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

Порядок выполнения логических операций:
Действия в скобках.
Инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.

поедет в деревню и, если будет хорошая погода, то он

Это составное высказывание состоит из простых высказываний:
А = «Петя поедет в деревню»
В = «Будет хорошая погода»
С = «Он пойдет на рыбалку»
Записываем высказывание в виде логического выражения, учитывая порядок действий
F = A ^ (B → C)

2n, где n – количество логических переменных.
Определить количество столбцов таблицы:

(количество строк без шапки)= 22 = 4.
Операций – 2, значит

Пример построения
таблицы истинности

с использованием электронных таблиц. Количество логических переменных 3, следовательно, количество строк

т.к. в формуле две переменные A и B.
Количество столбцов: 2

последние столбцы таблиц истинности совпадают, обозначают “=“.
Докажите равносильность выражений:
Таблица истинности

Таблица истинности для