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

Соколова Валентина Александровна

опорные конспекты к дисциплине основы электроники и цифровой схемотехники

Скачать:

ВложениеРазмер
Microsoft Office document icon опорные конспекты 422.5 КБ
Office presentation icon презентация к уроку2.9 МБ

Предварительный просмотр:

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

Этапы развития логики  

1

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

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

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

2

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

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

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

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

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

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

3

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

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

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

Введение в алгебру высказываний

Логика изучает абстрактное мышление как средство познания  объективного мира.


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


Примеры высказываний

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

Истинно

2 + 8 < 5

Ложно

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

Истинно

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

Ложно

Примеры, не являющиеся высказываниями

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

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


Примеры сложных  высказываний

Простые высказывания:

  1. На улице идет дождь.

  1. На улице светит солнце.

  1. На улице пасмурная погода.

  1. На улице идет снег.

Задание

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


Примеры

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

Обозначение

Значение

Запись

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

А

Истина

А = 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;

A

B

C

1

2

3

0

0

0

0

1

1

1

1


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

 

A

B

C

1

2

3

0

0

0

0

0

1

0

1

1

0

1

0

1

1

1

1

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

 

A

B

C

1

2

3

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

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

A

B

C

1

2

3

0

0

0

1

0

0

0

0

1

0

0

0

0

1

0

1

1

1

0

1

1

0

0

0

1

0

0

1

0

1

1

0

1

0

0

1

1

1

0

1

1

1

1

1

1

0

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 года

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

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

При разработке релейно-контактных схем широко применялась алгебра логики.

«Символический анализ релейно-контактных схем» (декабрь 1938 год, Клод Шенон) – первое фундаментальное исследование, обратившим внимание инженеров, занимавшихся проектированием ЭВМ, на возможность анализа электрических цепей с помощью булевой алгебры.


Построение функциональных схем 

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

На вход каждого элемента подаются сигналы, называемые входными.

На выходе получаем выходной сигнал.

Если есть сигнал – значит 1, если нет сигнала - 0.

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


4. Решение задач.

Написать логические формулы выходных сигналов:

X

Y

Z

A

B

C

X

A

B

X

Y

Z

Нарисовать схему для логической функции:


СДНФ  и  СКНФ

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

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

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

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

Примеры

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

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

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

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

Примеры

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

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

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

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

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

  1. если  значение переменной равно 0, то записывается сама переменная,
  2. если значение переменной равно 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

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


 Анализ, упрощение, синтез логических схем

Этап

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

Пример

Анализ

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

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

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

X

Y

0

0

1

1

0

0

1

1

1

0

1

0

0

0

0

1

1

0

1

1

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

Упрощение

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

Синтез

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

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

X

Y

F(X,Y)

0

0

0

0

1

1

1

0

1

1

1

1

СКНФ

СДНФ

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


Предварительный просмотр:


Подписи к слайдам:

Слайд 1

Логика

Слайд 2

Логика –наука, изучающая законы и формы мышления. Логика изучает: Формы мышления Способы мышления

Слайд 3

1 этап – формальная логика Основатель – Аристотель (384 -322гг. до н.э. ) Ввёл основные формулы абстрактного мышления

Слайд 4

2 этап – математическая логика Основатель – немецкий ученый и философ Лейбниц(1642 -1716), предпринял попытку логических вычислений.

Слайд 5

3 этап - Алгебра высказываний (Булева алгебра) Основатель - английский математик Джордж Буль(1815 – 1864), ввёл алфавит, орфографию и грамматику для математической логики.

Слайд 7

Понятие- это форма человеческого мышления, где фиксируются основные, существенные признаки объекта. Любое понятие состоит из двух составляющих: объёма понятия и содержания понятия .

Слайд 8

Объем понятия - это совокупность (множество) предметов, на которое оно распространяется. Содержание понятия - это совокупность основных, существенных признаков объекта.

Слайд 9

Умозаключение- это форма мышления, с помощью которой из одной или нескольких суждений (посылок) может быть получено новое суждение (заключение).

Слайд 10

Высказывание- это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных объектов и отношениях между ними. Высказывание может быть либо истинным, либо ложным. Высказывание не может быть выражено повелительным или вопросительным предложением, т. к. оценка их истинности или ложности невозможна.

Слайд 11

Высказывания могут быть простыми или составными . 2+2=4 – это пример простого высказывания. Простое высказывание содержит одну простую мысль . Составные высказывания состоят из простых высказываний и логических операций. “ На улице солнечно и у меня хорошее настроение. ” – это пример составного высказывания. Алгебра высказываний определяет истинность или ложность составных высказываний.

Слайд 12

Математический аппарат логики: Вводятся вместо простых высказываний логические переменные: А, В, С и т.д. Значения высказываний обозначаются следующим образом: истина- 1 ложь- 0 .

Слайд 13

Название Обозначение Математическое обозначение Логическое умножение, конъюнкция и &, Ÿ ,/\ Логическое сложение, дизъюнкция или +,\/ Логическое отрицание, инверсия не  Импликация, следование если, то  Эквивалентность, равносильность тогда и только тогда 

Слайд 14

Информатика изучается в курсе средней школы. «Е»- шестая буква алфавита. Квадрат является ромбом. Квадрат гипотенузы равен сумме квадратов катетов. Сумма углов треугольника равна 190 0 . 12+14>30 Графическое изображение векторной графики формируется из точек(пикселей). 16-битные звуковые карты точнее кодируют и воспроизводят звук, чем 8-битные.

Слайд 15

Здравствуй! Аксиома не требует доказательств. Идёт дождь. Какая температура на улице? Число 2 является делителем числа 9. Число х не больше двух. Уходя гасите свет.

Слайд 16

Кто является основателем формальной логики? Дайте определение логики как науки. Каково её назначение? Какие существуют основные формы мышления? Что такое высказывание? Приведите примеры высказываний и предложений, не являющихся ими.

Слайд 17

Джордж Буль и его необыкновенная алгебра. Развитие логических систем (учений) от Аристотеля. Тавтологии, силлогизмы и парадоксы.

Слайд 18

Н. Д. Угринович Информатика и информационные технологии. Учебник для 10-11 классов. И.А. Иванова Информатика 10 класс. Практикум. В.М. Казиев Информатика в примерах и задачах. Книга для учащихся 10-11 класс


По теме: методические разработки, презентации и конспекты

Алгебра логики: минимизация булевых функций

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

Презентация к уроку "Нормальные формы для формул алгебры логики"

Презентацияк уроку по дисциплине ЕН.02 Элементы математической логики на тему "Нормальные формы для формул алгебры логики". Тема расчитана на 2 академических часа....

Презентация по информатике на тему "Элементы алгебры логики. Высказывания. Логические операции"

Презентация по информатике на тему "Элементы алгебры логики. Высказывания. Логические операции"...

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

презентация на тему: Алгебра логики...

Логические основы алгебры логики

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

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

для студентов...

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

для студентов...