%D0%9B%D0%9A_%E2%84%964_%D0%9B%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0

1.

ДИСЦИПЛИНА · ИНФОРМАТИКА
ЛЕКЦИЯ 3
Логические основы ЭВМ.
Минимизация булевых функций
Булева алгебра, логические элементы и схемы, совершенные нормальные формы,
метод карт Карно

2.

Лекция 3 · Содержание
02 / 24
Содержание лекции
▦
1. Основы алгебры логики (1–5)
2. Булевы функции и таблицы истинности (6)
3. Логические элементы и схемы (7–10)
4. Законы алгебры логики (11)
5. Унифицированные формы: ДНФ/КНФ, СДНФ/СКНФ (12–17)
6. Минимизация булевых функций (18–19)

3.

01 / 06
Основы алгебры логики
Формы мышления, логическое высказывание, переменная и функция.
Джордж Буль и базовые понятия алгебры логики.
1КВ 1
2КВ 2
3КВ 3
4КВ 4
5КВ 5

4.

Подраздел 1 · Основы алгебры логики
03 / 24
Формы мышления и алгебра логики
ФОРМЫ МЫШЛЕНИЯ
1
● Понятие — фиксация существенных признаков
объекта
● Высказывание — утверждение о свойствах
предметов и отношениях между ними (может быть
истинным или ложным)
● Умозаключение — получение нового суждения на
основе одного или нескольких суждений
3
2
ЛОГИКА И АЛГЕБРА ЛОГИКИ
● Логика — наука о формах и способах мышления
(предложена Аристотелем)
● Математическая логика (МЛ) — современная форма
логики, опирается на формальные математические методы
● Алгебра логики (булева алгебра) — раздел МЛ,
изучающий строение сложных логических высказываний с
точки зрения их истинности/ложности алгебраическими
методами
ДЖОРДЖ БУЛЬ (1815–1864)
Английский математик. Внёс в логику новые понятия, разработал математический
аппарат для формализации действий над логическими выражениями — основу для
разработки логических элементов в цифровых устройствах.

5.

04 / 24
Подраздел 1 · Основы алгебры логики
Логические высказывание, переменная, функция и операция
4
ВЫСКАЗЫВАНИЕ И ПЕРЕМЕННАЯ
5
ЛОГИЧЕСКАЯ ФУНКЦИЯ И ОПЕРАЦИЯ
● Логическое высказывание — утверждение,
относительно которого можно говорить о его истинности (1)
или ложности (0). Характеризует свойства или состояние
объекта.
● Логическая функция (ЛФ) — составное высказывание,
состоящее из логических переменных, связанных
логическими операциями. Записывается в виде логической
формулы. Принимает значение 0 или 1: f(x₁, x₂, …, xₙ).
● Логическая переменная — простое высказывание,
принимающее значение 0 или 1.
● Набор значений аргументов ЛФ x₁, x₂, …, xₙ — двоичное
число. Число всех наборов аргументов — 2ⁿ.
● Пример. «2 < 4» — простое высказывание (константа).
● Логическая операция — элементарная логическая связь
между логическими переменными.
А = (x < 2) — логическая переменная: 0 при x = 5, 1 при x = 0.
f(x₁, x₂, …, xₙ) ∈ {0, 1} · всего наборов = 2ⁿ
⇄ ОТЛИЧИЕ
Логическая операция — это элементарная связь между переменными (унарная/бинарная), а логическая
функция — составное выражение, в которое могут входить несколько операций.

6.

02 / 06
Булевы функции и таблицы истинности
Восемь основных операций булевой алгебры, их обозначения и таблицы
истинности. Базисы Шеффера и Пирса.
6КВ 6

7.

Подраздел 2 · Булевы функции
Таблица истинности. Базовые операции
6а
06 / 24
Таблица истинности (ТИ) описывает значения ЛФ для всех 2ⁿ наборов значений
её аргументов.
Ниже — три базовые операции булевой алгебры.
✦ КОНЪЮНКЦИЯ ∧
✦ ДИЗЪЮНКЦИЯ ∨
Обозначения:
⊘
ИНВЕРСИЯ ¬
Обозначения:
Обозначения:
x ∨ y, x + y
x ∧ y, x & y, x·y, xy
(в ЯП: x AND y, x && y)
¬x,