Логические функции. Основные соотношения алгебры логики

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

ПЛАН:

1. Основные понятия алгебры логики

2. Операции булевой алгебры. Логические схемы.

Логические функции. Основные соотношения алгебры логики

4. Упрощение логических формул

!!! Алгебра логики – это раздел математической логики, значения всех элементов которой определены в двухэлементном множестве 0 и 1.

Аппарат булевой алгебры служит для анализа и синтеза комбинационных логических схем. Он описывает поведение некоторого множества объектов с двумя логическими состояниями: «истина» и «ложь». Эти два состояния могут соответственно трактоваться логикой высказывания «да» и «нет». Два значения логики высказывания интерпретируются двумя значениями двоичных цифр: 1 и 0. 1 – «да», 0 – «нет»

Джордж Буль (1815-1864). Английский математик. Говоря о творчестве Джорджа Буля, исследователи истории вычислительной техники непременно подчеркивают, что этот выдающийся английский ученый первой половины ХIХ века был самоучкой. Возможно, именно благодаря отсутствию «классического» (в понимании того времени) образования, Джордж Буль внес в логику, как в науку, революционные изменения.

Занимаясь исследованием законов мышления, он применил в логике систему формальных обозначений и правил, близкую к математической. Впоследствии эту систему назвали логической алгеброй ила булевой алгеброй. Правила этой системы применимы к самым разнообразным объектам и их группам (множествам, по терминологии автора). Основное назначение системы, по замыслу Дж. Буля, состояло в том, чтобы кодировать логические высказывания и сводить структуры логических умозаключений к простым выражениям, близким по форме к математическим формулам. Результатом формального расчета логического выражения является одно из двух логических значений: истина или ложь.

Значение логической алгебры долгое время игнорировалось, поскольку ее приемы и методы не содержали практической пользы для науки и техники того времени. Однако, когда появилась принципиальная возможность создания средств вычислительной техники на электронной базе, операции, введенные Булем, оказались весьма полезны. Они изначально ориентированы на работу только с двумя сущностями: истина и ложь. Нетрудно понять, как они пригодились для работы с двоичным кодом, который в современных компьютерах тоже представляется всего двумя сигналами: ноль и единица. Не вся система Джорджа Буля (как и не все предложенные им логические операции) были использованы при создании электронных вычислительных машин, но четыре основные операции: И (пересечение), ИЛИ (объединение), НЕ (обращение) и ИСКЛЮЧАЮЩЕЕ ИЛИ - лежат в основе работы всех видов процессоров современных компьютеров.

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

!!! Логическое высказывание – это любое повествовательное высказывание, относительно которого можно однозначно сказать, истинно оно или ложно.

НАПРИМЕР: «Лед – твердое состояние воды» - истинное высказывание

«Все рыбы умеют плавать» - общее высказывание (истинное)

«Париж – столица Китая» - ложное высказывание

Истинному высказыванию приписывают значение «1», ложному – значение «0»

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

!!! Логическая константа – ИСТИНА (1) или ЛОЖЬ (0)

!!! Логическая переменная – символически обозначенная логическая величина, которая может принимать только значения ИСТИНА (1) или ЛОЖЬ (0)

ПРИМЕР: Пусть А – Петров врач, В – Петров – шахматист. Тогда можно (например при помощи связки «и») составить составное высказывание: Петров – врач И шахматист (мы это поймем как «Петров – врач, умеющий играть в шахматы), А при помощи введенных обозначений мы получим: А И В

!!! Логическое выражение – простое или сложное высказывание. Сложное высказывание строится из простых с помощью логических операций – связок

Логические выражения являются функциями логических переменных, обозначаемых А, В, С, Х и т.д., каждая из которых принимает значения 0 или 1.

Для К логических переменных существует 2^К логических комбинаций 0 и 1.

НАПРИМЕР: К=2 (высказывания А и В)→ различных комбинаций – 4 (00, 01, 10, 11)

К=3 (А, В, С) → комбинаций 2³=8 (000, 001, 010, 011, 100, 101, 110, 111)