Логические основы ПК

11/13/18

Алгебра логики

Логические операции

Задание : Являются ли следующие предложения высказываниями?

• На улице светит солнце.
• Уходя гасите свет.
• Из окна виден парк.
• Какого цвета этот дом?
• Посмотрите в окно.

Х

Х

Х

Логическая переменная – это простое высказывание. Значением логической переменной могут быть только константы ИСТИНА (1) или ЛОЖЬ (0) .

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

Логическая операция – логическое действие. Существуют три базовые логические операции – конъюнкция , дизъюнкция , инверсия , остальные операции являются дополнительными: импликация , эквивалентность и другие.

Логическое отрицание - ИНВЕРСИЯ

Образуется из высказывания с помощью добавления частицы «НЕ» к сказуемому или использования оборота речи «НЕВЕРНО, ЧТО...»

Примеры инверсии:

А= «Неверно, что у меня есть приставка Dendy»

В= «Я не знаю китайского языка»

Обозначение : Ā, ¬А, не А, not А

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

Инверсия высказывания истинная, когда высказывание ложно, и ложна, когда высказывание истинно.

А

0

⌐ А

1

1

0

Логическое умножение - КОНЪЮНКЦИЯ

Образуется соединением двух высказываний в одно с помощью союза «И» (а также «А», «НО» )

Примеры конъюнкции:

А= «Сегодня солнечный день и мы пойдем гулять»

В= «Богдан был победителем, а Степан занял второе место»

Обозначение : А и В , А  В,

А & В, А*В, А and B

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

А

0

В

А&В

0

0

0

1

1

1

0

0

0

1

1

Конъюнкция двух высказываний истинная тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно.

Логическое сложение - ДИЗЪЮНКЦИЯ

Образуется соединением двух высказываний в одно с помощью союза «ИЛИ» (нестрогая), «ЛИБО» (строгая)

Обозначение : А или В , А  В,

А+В, А or B

Примеры дизъюнкции:

А= «Снег пойдет ночью или утром»

В= «Он приедет сегодня либо завтра»

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

А

0

В

А  В

0

0

0

1

1

1

0

1

1

1

1

Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно.

Логическое следование - ИМПЛИКАЦИЯ

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

Примеры импликации:

А= «Если число делится на 9, то оно делится на 3»

В= «Если на улице дождь, то асфальт мокрый»

Обозначение : А  В , А  В

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

А

0

В

А  В

0

0

1

1

1

1

0

1

0

1

1

Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное.

Логическое равенство - ЭКВИВАЛЕНТНОСТЬ

Образуется соединением двух высказываний в одно с помощью оборота речи:

«… ТОГДА И ТОЛЬКО ТОГДА, КОГДА ...»

Обозначение : А  В , А  В,

А=В, А  В,

Примеры эквивалентности:

А= «Число кратно 3 тогда и только тогда, когда сумма цифр числа делится нацело на 3»

В= «Угол называется прямым тогда и только тогда, когда он равен 90°»

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

А

0

В

А  В

0

0

1

1

1

1

0

0

0

1

1

Эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны.

Для наглядной геометрической иллюстрации объемов понятий и соотношений между ними используются диаграммы (круги) Эйлера-Венна. Если имеются какие-либо понятия А, В и так далее, то объем каждого понятия (множество) можно представить в виде круга, а отношения между этими объемами (множествами) в виде пересекающихся кругов.

Конъюнкция

Дизъюнкция

Инверсия

Приоритет логических операций

• инверсия
• конъюнкция
• дизъюнкция
• импликация
• эквивалентность

Операции одного приоритета выполняются слева направо.

Для изменения порядка действий используются скобки.

Пример 1

4

5

3

2

1

Дана формула: А  В → С & D ↔ Ā

1

2

3

4

5

Дана формула: А  (В → С) & D ↔ Ā

Задача № 1

Какие из приведенных высказываний не являются формулами алгебры логики.

• А+→В +А+В А-В А&В А+В+С А*В ¬А+В (А+В)&C
• А+→В +А+В А-В А&В А+В+С А*В ¬А+В (А+В)&C
• А+→В +А+В А-В А&В А+В+С А*В ¬А+В (А+В)&C
• А+→В +А+В А-В А&В А+В+С А*В ¬А+В (А+В)&C
• А+→В
• +А+В
• А-В
• А&В
• А+В+С
• А*В
• ¬А+В
• (А+В)&C

Задача № 2

Запишите на языке алгебры логики следующие высказывания.

• На улице идет дождь и дует сильный ветер или светит солнце.
• Я поеду в Москву и встречу там друзей.
• Я не пойду в школу или не пойду в кино.
• Мы едем в театр и не можем ехать в зоопарк.

1&((x1) 1 2) 2 3) 3 4) 4." width="640"

Задача № 3

Для какого числа Х истинно высказывание x1&((x

1) 1 2) 2 3) 3 4) 4.

Задача № 4

Найдите значение логических выражений

• F = (0  0)  (1  1)
• F = (1  1)  (1  0)
• F = (0 & 0) & (1 & 1)
• F =  1 & (1  1)  (  0 & 1)
• F = (  1  1) & (1   1) & (  1  0)

11/13/18

Алгебра логики

Построение таблиц истинности

Установите соответствие

между определениями или обозначения

 Задание 1

Укажите в нижеприведенных сложных высказываниях связующие слова или союзы и логическую операцию:

• Если горит свет, то электроэнергия поступает.
• Всякий прямоугольник имеет прямые углы и параллельные друг другу стороны.
• Треугольники с равными сторонами не являются равнобедренными.
• На следующем уроке будет либо история, либо химия.
• Я поеду в горы тогда и только тогда, когда куплю горные лыжи и ботинки.
• Неверно, что Саша приходил вчера ко мне.
• Зимой мы обычно ходим на лыжах или катаемся на коньках на нашем пруду.
• x + y =  /2 и sin x - sin y = 2 1/2

 Задание 2

Составьте несколько сложных высказываний, используя нижеприведенные простые высказывания и логические связки:

1. Завтра будет хорошая погода.

Мы хотим пойти за грибами.

• Сергей приглашает нас на рыбалку. Сергей приглашает нас купаться.

3. 2 * 2 = 5.

Н 2 О = водород + кислород.

4. Я видел Мишу в школе.

Он скоро окончит институт.

Он будет учиться в аспирантуре.

5. Завтра будет холодно.

Завтра будет снег.

Завтра будет тепло.

 Задание 3

По форме высказывания и выраженным на естественном языке составляющим его простым высказываниям получите фразу на естественном языке:

(B & Ē)  Ā

Составляющие простые высказывания:

А = «Некто является врачом»;

В = «Больной поговорил с врачом»;

Е = «Больному стало легче».

 Задание 4

По мишеням произведено три выстрела. Рассмотрено высказывание: Рк= «мишень поражена к -ым выстрелом», где к=1,2,3. Что означают следующие высказывания.

Р1  Р2  Р3

Одним из трех выстрелов попали в мишень

Р1 & Р2 & Р3

Всеми тремя выстрелами попали в мишень

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

Алгоритм построения таблицы истинности для логического выражения:

• Количество переменных (n) = …
• Количество строк (m) = 2 n + 1 (строка заголовка)
• Количество столбцов = … лог. переменные + ... лог. операций = …
• Укажем порядок действий:
• Заполним таблицу:

Построим таблицу истинности для

логического выражения: X v Y&  Z

3

Количество переменных (n) =

Количество строк (m) =

Количество столбцов =

Укажем порядок действий: X v Y & ⌐Z

Заполним таблицу:

9 (2 3 +1строка заголовка)

6

1

2

3

X

0

Y

0

Z

0

0

(1)

0

0

0

(2)

1

1

1

(3)

1

0

1

1

0

1

0

0

1

1

1

1

0

1

Тождественно истинные, тождественно ложные и эквивалентные высказывания

Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1).

Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).

Если значения сложных высказываний совпадают на всех возможных наборах значений входящих в них переменных, то такие высказывания называется равносильными, тождественными, эквивалентными.

 Задание 1

Постройте таблицы истинности следующих сложных высказываний и определите, являются ли эти высказывания тождественно истинными:

1. A & B  A

2. B  (B v A)

А

0

В

0

0

1

1

1

0

1

А

0

В

0

0

1

1

1

0

1

 Задание 2

Определите равносильны ли следующие логические выражения:

А

0

В

0

0

1

1

0

1

1

А

0

В

0

0

1

1

1

0

1