Логические основы ЭЦВМ

Джордж Буль
1815 -1864
«Имеется глубокая аналогия между символическим методом алгебры и символическим методом представления логических форм …
В такой символике высказывания могут быть сведены к форме уравнений»

Алгебра высказываний
(Алгебра логики, Булева алгебра)
Высказывания представляются логическими переменными, которые могут иметь всего два значения:
истина true (1)
ложь false (0)

Простые высказывания
Волга впадает в Каспийское море a=1
Амур впадает в Каспийское море a=0
Возможно осложнение заболевания a={0,1}
Сложные высказывания
Волга впадает в Каспийское море и Амур впадает в Каспийское море
Волга впадает в Каспийское море или Амур впадает в Каспийское море

Отношение – список истинных выражений (фактов), касающихся некоторого признака группы объектов
Иван – мужчина
Мария – женщина
Ирина – женщина
Петр – мужчина
Василий – мужчина
………….
Отношение Пол для группы пациентов
(Соответствующее поле в записях компьютерной базы данных)

Предикат – логическая функция, определенная над отношением
Предикат имеет значение Истина, если его аргумент принадлежит отношению, в противном случае – значение Ложь
Пример: предикат a( x – мужчина ) = 1, если x – Иван; = 0, если x – Мария

Базовые операции алгебры логики
(задаются таблицами истинности) Логическое ИЛИ Логическое И Логическое НЕ (дизъюнкция V, |, OR) (конъюнкция ^,&, AND) (инверсия ¬, NOT)
Логические элементы:

Операции с константами: a + 0 = a a + 1 = 1 a * 0 = 0 a * 1 = a
Закон исключенного третьего: a + a = 1
Закон непротиворечия: a * a = 0
Законы идемпотенции: a + a = a a * a = a
Закон двойного отрицания: a = a
Законы де Моргана: a + b = a * b a * b = a + b
Закон поглощения: a + a * b = a
Закон склеивания: a * b + a * b = a
ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Сын: можно мне пойти в кино или купить мороженое?
Мама: нет
Нельзя пойти в кино и нельзя купить мороженое

Порядок выполнения операций можно изменять с помощью скобок:
Переместительный закон: a + b = b + a
Сочетательный закон: a+(b+с)=(a+b)+с
Дистрибутивныйзакон: a*(b+с)=(a*b)+(а*с) a + b*с = (a + b)*с a + b=(a + b)

Любая сколь угодно сложная логическая функция,
заданная своей таблицей истинности,
может быть представлена логическим выражением в совершенной дизъюнктивной нормальной форме (СДНФ)

S = abp+abp+abp+abp
P = abp+abp+abp+abp =
= ab+ap+bp
Пример: таблица истинности одноразрядного сумматора
Построение СДНФ:
для всех строк с единичными значениями выходной функции выписывается логическая сумма (дизъюнкция) из логических произведений (конъюнкций) всех входных переменных, при этом входная переменная пишется с инверсией, если ее значение в соответствующей строке равно нулю

Логическая операция «Импликация»: а -> b
a – Посылка
b – Следствие
Если a, то b
Посылка является условием, достаточным для выполнения следствия;
Следствие является условием, необходимым для истинности посылки.
Если заболевание – тяжелое, то возможны осложнения

Импликация над предикатами называется продукционным правилом
Пример: Если ( x – мужчина ) И ( x – имеет детей ), то ( x – отец )
Система продукционных правил лежит в основе компьютерной базы знаний

Тестовые задания по теме лекции

Результат логической операции ДИЗЪЮНКЦИЯ (логическое ИЛИ) от двух переменных равен ИСТИНА, если
|1. Значение хотя бы одной из переменных равно ИСТИНА
|2. Значение обоих переменных равно ИСТИНА
|3. Значение только одной из переменных равно ЛОЖЬ
|4. Значение обоих переменных равно ЛОЖЬ

Результат логической операции КОНЪЮНКЦИЯ (логическое И) от двух переменных равен ИСТИНА, если
|1. Значение хотя бы одной из переменных равно ИСТИНА
|2. Значение обоих переменных равно ИСТИНА
|3. Значение только одной из переменных равно ЛОЖЬ
|4. Значение обоих переменных равно ЛОЖЬ

Результат логической операции ДИЗЪЮНКЦИЯ с ИНВЕРСИЕЙ (логическое ИЛИ-НЕ) от двух переменных равен ИСТИНА, если
|1. Значение хотя бы одной из переменных равно ИСТИНА
|2. Значение обоих переменных равно ИСТИНА
|3. Значение только одной из переменных равно ЛОЖЬ
|4. Значение обоих переменных равно ЛОЖЬ

Результат логической операции КОНЪЮНКЦИЯ с ИНВЕРСИЕЙ (логическое И-НЕ) от двух переменных равен ИСТИНА, если
|1. Значение только одной из переменных равно ИСТИНА
|2. Значение обоих переменных равно ИСТИНА
|3. Значение хотя бы одной из переменных равно ЛОЖЬ
|4. Значение обоих переменных равно ЛОЖЬ

В результате поиска в базе данных пациентов по условию ВОЗРАСТ больше 30 лет И ВОЗРАСТ меньше 20 лет будут отобраны
|1. Одна запись
|2. Ни одной записи
|3. Все записи

В результате поиска в базе данных пациентов по условию ВОЗРАСТ больше 30 лет ИЛИ ВОЗРАСТ меньше 40 лет будут отобраны
|1. Одна запись
|2. Ни одной записи
|3. Все записи

В приведенных ниже логических равенствах
(знак дизъюнкции +, знак конъюнкции *)
неверным является
|1. a + 1 = 1
|2. a + a = a
|3. a * 1 = 1
|4. a + a * b = a

Тестовые задания
с единого портала
интернет-тестирования
в сфере образования

Правильный ответ 3

Правильный ответ 1

По формуле де Моргана для выражения в скобках
правильный ответ 4

Правильный ответ 3