Таблицы истинности логических функций и логические элементы

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

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

Таблица истинности состоит их двух частей. Первая (левая) часть относится к логическим переменным и содержит полный перечень возможных комбинаций логических переменных А, В, С, ¼ и т.д. Вторая (правая)часть этой таблицы определяет выходные состояния как логическую функцию от комбинаций входных величин.

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

Ø таблица истинности логической функции одного аргумента состоит из двух строк: два различных значения аргумента – «истина» (1) и «ложь» (0) и два соответствующих им значения функции, т.е. данная таблица истинности содержит 2 строки и 2 столбца;

Ø в таблице истинности логической функции двух аргументов – четыре различных сочетания значений аргументов – 00, 01, 10 и 11 и четыре соответствующих им значения функции, т.е. данная таблица истинности содержит 4 строки и 3 столбца;

Ø если число высказываний в логической функции N, то существует 2^N различных комбинаций возможных значений аргументов, т.е. таблица истинности будет содержать 2^N строк, где N – число аргументов логической функции, а число столбцов равно N + 1.

Таблицу истинности можно составить для любой логической функции.

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

1. Логическая операция ИНВЕРСИЯ (НЕ).

Таблица истинности для логической функции F = Ø A.

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

В ЭВМ операция инверсии физически реализуется стандартным логическим элементом – инвертором.

Рис 9. Графическое обозначение элемента НЕ

Принцип работы схемы элемента НЕ следующий: если на входе схемы НЕ ноль, то на выходе единица, когда на входе единица, то на выходе ноль.

2. Логическая операция КОНЪЮНКЦИЯ (И).

Таблица истинности для логической функции F = A & B.

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

В ЭВМ операция конъюнкции физически реализуется стандартным логическим элементом – конъюнктером.

Рис 10. Графическое обозначение двухвходового элемента И

Принцип работы схемы элемента И следующий: единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе будет ноль.

Конъюнктер теоретически может иметь бесконечное число входов, на практике ограничиваются числом входов от двух до восьми.

3. Логическая операция ДИЗЪЮНКЦИЯ (ИЛИ).

Таблица истинности для логической функции F = А Ú В.

Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В – ложны.

В ЭВМ операция дизъюнкции физически реализуется стандартным логическим элементом – дизъюнктером.

Рис 11. Графическое обозначение двухвходового элемента ИЛИ

Принцип работы схемы элемента ИЛИ следующий: если хотя бы на одном входе схемы ИЛИ будет единица, на ее выходе также будет единица. Ноль на выходе будет только тогда, когда на всех входах схемы ИЛИ будут нули.

Дизъюнктер теоретически может иметь бесконечное число входов, на практике ограничиваются числом входов от двух до восьми.

4. Логическая операция ИМПЛИКАЦИЯ (ЕСЛИ-ТО).

Таблица истинности для логической функции F = А → B

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

5. Логическая операция ЭКВИВАЛЕНЦИЯ (логическая равнозначность).

Таблица истинности для логической функции F = А ↔ B.

Результат операции эквиваленция истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Три приведенные выше логических элемент составляют функционально полную систему для проектирования цифровых логических устройств, в том числе и соответствующих логических блоков и устройств компьютера, поскольку реализуют функционально полный набор логических функций, состоящий из логических функций: И (конъюнкция), НЕ (отрицание), ИЛИ (дизъюнкция).

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

В настоящее время существует достаточно много программных продуктов, с помощью которых можно реализовать различные логические функции и форму их представления, например в виде таблиц истинности. Логические функции широко используются и в программе MS Excel. Для вызова этих функций необходимо выполнить следующие команды: Кнопка Пуск – Программы – MS Office – MS Excel и далее команду Вставка – Функция – Категория: Логические и далее можно выбрать необходимую логическую функцию. В этом же окне можно получить справку по каждой из этих функций.

Как видно из рисунка 12, в состав логических функций программы MS Excel входит функционально полный набор логических функций.

Рис 12. Диалоговое окно «Мастер функций». Категория: Логические

Таким образом, с помощью функционально полного набора логических функций программы MS Excel можно реализовать другие функции.

Реализуем с помощью логических функций ЕСЛИ и И модифицированную таблицу истинности логической функции F = A& B (конъюнкция), состоящую из двух строк и трех столбцов, которая позволяет при изменении значений (0 или 1) логических переменных А и В автоматически устанавливать, например, в ячейке Е6 значение функции F = A& B, соответствующее значениям этих логических переменных. Для этого в ячейку Е6 введем следующее выражение: ЕСЛИ(И(С6; D6; 1; 0), тогда при вводе в ячейки С6 и D6 значений 0 и 1 в ячейке Е6 будет выполняться логическая функция F = A& B. Результат этих действий представлен на рисунке 13.

Рис 13. Реализация модифицированной таблицы истинности логической функции F = A & B

Рассмотрим на примерах три способа решения логических задач:

1) средствами алгебры логики;

2) табличный;

3) с помощью рассуждений.

Пример 2. В таблице приведены запросы к поисковому серверу:

А чемпионы | (бег & плавание)

Б чемпионы & плавание

В чемпионы | бег | плавание

Г чемпионы & Европа & бег & плавание

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

Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.

Решение.

Решение задачи сводится к тому, чтобы расположить множества, состоящие из результатов поиска А-Г в порядке возрастания количества элементов. Воспользуемся тем, что логическое умножение для двух множеств равносильно их пересечению, а логическое сложение – их объединению. При этом при пересечении несовпадающих множеств в результате всегда получается множество, меньшее, чем исходные множества, а при объединении – большие, чем исходные (рис. 14).

Рис 14. Результаты пересечения и объединения двух множеств

Введем обозначения для множеств и запросов. Пусть K = «чемпионы», L = «бег», M = «плавание», N = «Европа».

Тогда запрос к серверу выглядит следующим образом:

чемпионы | (бег & плавание) – А = K È L Ç M;

чемпионы & плавание – Б = K Ç M;

чемпионы | бег | плавание – В = K È L È M;

чемпионы & Европа & бег & плавание – Г = K Ç N Ç L Ç M.

Из обозначений запросов видно, что самым маленьким по количеству элементов будет множество Г(состоит из пересечений четырех множеств K, L, M, N). Самым большим множеством является множество В, так как оно состоит из объединений трех множеств K, L и M. Осталось определить, какие множества (из А и Б) будут стоять на 2 и 3 местах.

Заметим, что множество Б состоит из пересечений двух множеств K и M, поэтому оно является множеством, меньшим К. МножествоА состоит из объединения множества К с пересечением множеств L и M, поэтому А – множество, большее К. Значит, при расположении их в порядке возрастания, получим, что на втором месте в ответе будет стоять Б, а на третьем – А.

Ответ: ГБАВ.

Пример 3. В процессе составления расписания занятий преподаватели высказали свои пожелания. Преподаватель информатики хочет проводить первую или вторую пару, преподаватель математики – первую или третью, а преподаватель анатомии – вторую или третью пару. Сколько существует возможных вариантов расписания и каковы они?

Решение.

Введем обозначения: А – 1-я пара информатики, В – 2-я пара информатики, А –1-я пара математики, С – 3-я пара математики, В – 2-я пара анатомии, С – 3-я пара анатомии.

Составим логическую формулу, опираясь на условие задачи:

(А Ú В) & (А Ú C) & (В Ú С).

Таблица истинности для нее будет иметь вид: