алгебра логики
план-конспект урока на тему

1

Формальная логика

Наука о законах и формах мышления

В IV веке до нашей эры Аристотель (348-322 до н.э.) создал трактат, в котором попытался ответить на вопрос «Как мы рассуждаем?».

2

Математическая (символическая)  логика

Изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.

Готфрид Вильгельм Лейбниц (1646-1716)  сделал попытку построить первые логические  исчисления.

Он предложил заменить простые  рассуждения  действиями со знаками  и привел соответствующие  правила.

Джордж Буль (1815-1864) -  основоположник  математической логики как самостоятельной дисциплины.

В его работах логика обрела  свой алфавит, свою орфографию  и грамматику.

3

Применение математической логики

• математика: теория множеств, формальные системы, алгоритмы, рекурсивные функции.
• кибернетика, вычислительная техника и электротехника (построение компьютеров основано на законах математической логики).
• гуманитарные науки (логика, криминалистика).

Клод Эльвуд Шеннон в своей докторской диссертации, опубликованной в 1938 году изложил свои идеи о применении алгебры логики в электрических цепях. Данная работа считается поворотным пунктом в развитии вычислительной технике.

Земля – планета Солнечной системы

Истинно

2 + 8 < 5

Ложно

Всякий квадрат есть ромб

Истинно

Каждый ромб есть квадрат

Ложно

Уходя, гасите свет.

Да здравствует мыло душистое и полотенце пушистое!

Высказывание

Обозначение

Значение

Запись

У кошки четыре ноги.

А

Истина

А = 1

Москва расположена на двух холмах.

В

Ложь

В = 0

A

B

A   ∨  B

0

0

0

0

1

1

1

0

1

1

1

1

A

¬A

0

1

1

0

А

В

A ∧  B

0

0

0

0

1

0

1

0

0

1

1

1

Последовательность действий

Пример

Определяем количество переменных в логической функции – N.

N = 3

Определить количество строк (Q) в таблице:

Q= 2N

Q = 23 = 8

Определяем количество логических операций (К) и последовательность их выполнения.

                                            1

                                               2

                                           3

K = 3

Определяем количество столбцов:

N + K

N + K = 6

Заполняем исходные данные таблицы:

1. разделить колонку значений первой переменной пополам и заполнить верхнюю половину 0, нижнюю половину  1;

2. в следующей колонке для второй переменной половинку  снова делить пополам и заполнить четырьмя группами  0 и 1 вперемежку, начиная опять с группы 0;

3. так делать до тех пор, пока группы 0 и 1 не будут состоять из одного символа.

Выполнять логические операции для каждого столбца.

Логические

 выражения

Алгебраические

 выражения

Переместительный закон

(коммутативный)

A ∨  B = B ∨  A

A + B = 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  ∧  C)

(A ∙ B) ∙ C = A ∙ (B ∙ C)

Распределительный закон

(дистрибутивный)

(A ∨ B) ∧ C = (A ∧ C) ∨  (B ∧ C)

(A + B) ∙ C = (A ∙ C) + (B ∙ C)

(A ∧ B) ∨  C = (A ∨  C) ∧ (B ∨  C)

аналога нет

Закон инверсии   или формулы де Моргана

A  ∨  B = A  ∧  B

A ∧   B = A∨  B

Закон двойного отрицания

Закон исключения констант

Для логического сложения

Х ∨  0 = Х                          Х ∨  1 = 1

Для логического умножения

Х ∧ 0 = 0                             Х ∧ 1 = Х

Закон идемпотентности

От лат. idem potens - равносильный

Для логического сложения

Х ∨  Х = Х

Для логического умножения

Х ∧ Х = Х

Закон противоречия

Невозможно, чтобы противоречивые высказывания были одновременно истинными

Закон исключения третьего

Из двух противоречивых высказываний об одном и том же предмете одно высказывание истинно, а второе – ложно, третье не дано.

Закон поглощения

Закон исключения

Поколение

Элементная база

Быстродействие (операций в секунду)

Объем ОП

Устройства

ввода-вывода

Программное обеспечение

Примеры

Первое поколение, после 1946 года

Электронные лампы

10-20 тыс.

2 Кб

Перфолента, перфокарта, магнитная лента

Машинные языки

ENIAC (США)
МЭСМ, БЭСМ (СССР)

Второе поколение, после 1955 года

Транзисторы

100-500 тыс.

2-32 Кб

Магнитный барабан, магнитный диск

Алгоритмические языки, диспетчерские системы, пакетный режим

IBM 701 (США)
БЭСМ-6, БЭСМ-4, Минск-22, Минск-32 (СССР)

Третье поколение, после 1964 года

Интегральные схемы (ИС)

1 млн.

64 Кб

Многотерминальные системы

Операционные системы,  режим разделения времени

IBM 360, PDP (США)
ЕС ЭВМ (СССР)

Четвертое поколение, после 1975 года

Большие интегральные схемы (БИС) и сверхбольшие интегральные схемы (СБИС)

10-100 млн.

16 Мб

Сети ПК

Базы и банки данных

ILLIAS 4 (США)

Эльбрус (СССР)

Пятое поколение, после 1982 года

Оптические, лазерные устройства

Экспертные системы

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

Элементарная конъюнкция – конъюнкция конечного множества логических переменных и их инверсий.

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

Ранг элементарной конъюнкции или дизъюнкции – число аргументов ее образующих.

Примеры

Элементарная конъюнкция третьего порядка

Элементарная дизъюнкция второго порядка

Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операциями конъюнкции.

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

Примеры

Совершенная конъюнктивная нормальная форма (СКНФ):

1) нет двух элементарных дизъюнкций;

2) ни одна элементарная дизъюнкция не содержит двух одинаковых переменных;

3) ни одна элементарная дизъюнкция не содержит переменную вместе с ее инверсией;

4) все дизъюнкции имеют один и тот же ранг.

Совершенная дизъюнктивная нормальная форма (СДНФ)

Алгоритм образования СКНФ и СДНФ по таблице истинности

1. Выделить в таблице истинности все строки, в которых функция принимает значения 0.

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

2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:

а) если  значение переменной равно 0, то записывается сама переменная,

б) если значение переменной равно 1, то записывается инверсия этой переменной.

2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные:

а) если  значение переменной равно 0, то записывается инверсия этой переменной,

б) если значение переменной равно 1, то записывается сама переменная.

3. Соединить элементарные дизъюнкции знаком конъюнкции.

3. Соединить элементарные конъюнкции знаком дизъюнкции.

X

Y

Z

F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

X

Y

Z

F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

X

Y

Z

F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

Этап

Наименование

Пример

Анализ

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

Схеме соответствует логическая функция:

По полученной формуле строится  таблица истинности, проводится анализ данной схемы:

Определяются исходные данные X и Y, при которых значение логической функции равно 1.        

Упрощение

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

Синтез

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

Для синтеза логической схемы используется СДНФ  или  СКНФ

СКНФ

СДНФ

Правильность проверяется сравнением исходной таблицы с таблицей истинности полученной функции.