Логические уравнения и программы и их схемы

Логические основы работы компьютера

Логические основы работы компьютера

Знания из области математической логики можно использовать для конструирования электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых «ложь» и «истина». Таким предметом, имеющим два фиксированных состояния, может быть электрический ток.

Логические элементы имеют один или несколько входов и один выход, через которые проходят электрические сигналы, обозначаемые условно 0, если «отсутствует» электрический сигнал, и 1, если «имеется» электрический сигнал.

Базовые логические элементы реализуют три основные логические операции: «И», «ИЛИ», «НЕ».

Логический элемент «НЕ» (инвертор)

Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот.

У этого элемента один вход и один выход. На функциональных схемах он обозначается:

Говорят также, что элемент «НЕ» инвертирует значение входной двоичной переменной.

Проверь соответствие логического элемента «НЕ» логическому элементу «НЕ». Воспользуйся тренажером Логические элементы.xlsx

Логический элемент «И» (конъюнктор)

Логический элемент «И» (конъюнктор) выдает на выходе значение логического произведения входных сигналов.

Он имеет один выход и не менее двух входов. На функциональных схемах он обозначается:

Сигнал на выходе конъюнктора появляется тогда и только тогда, когда поданы сигналы на все входы. На элементарном уровне конъюнкцию можно представить себе в виде последовательно соединенных выключателей. Известным примером последовательного соединения проводников является елочная гирлянда: она горит, когда все лампочки исправны. Если же хотя бы одна из лампочек перегорела, то гирлянда не работает.

Проверь соответствие логического элемента «И» логическому элементу «И». Воспользуйся тренажером Логические элементы.xlsx

Логический элемент «ИЛИ» (дизъюнктор)

Логический элемент «ИЛИ» (дизъюнктор) выдает на выходе значение логической суммы входных сигналов. Он имеет один выход и не менее двух входов. На функциональных схемах он обозначается:

Сигнал на выходе дизъюнктора не появляется тогда и только тогда, когда на все входы не поданы сигналы.

На элементарном уровне дизъюнкцию можно представить себе в виде параллельно соединенных выключателей.

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

Проверь соответствие логического элемента «ИЛИ» логическому элементу «ИЛИ». Воспользуйся тренажером Логические элементы.xlsx

Пример 1.
Составьте логическую схему для логического выражения: F=A \/ B /\ A.

1. Две переменные – А и В.

2. Две логические операции: 1-/\, 2-\/.

Пример 2.
Постройте логическую схему, соответствующую логическому выражению F=А/\В\/ ¬(В\/А). Вычислить значения выражения для А=1,В=0.

1. Переменных две: А и В; 1 4 3 2

2. Логических операций три: /\ и две \/; А/\В\/ ¬ (В\/ А).

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

4. Вычислим значение выражения: F=1 /\ 0 \/ ¬(0 \/ 1)=0

Логические схемы и таблицы истинности

Логические схемы создаются для реализации в цифровых устройствах булевых функций (функций алгебры логики).

В цифровой схемотехнике цифровой сигнал — это сигнал, который может принимать два значения, рассматриваемые как логическая «1» и логический «0».

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

Логические схемы реализуются на логических элементах: «НЕ», «И», «ИЛИ», «И-НЕ», «ИЛИ-НЕ», «Исключающее ИЛИ» и «Эквивалентность». Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе. Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).

На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.

Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.

Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:

• трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
• четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).

Рассмотрим построение (синтез) логических схем

• в булевом базисе «И», «ИЛИ», «НЕ» (в предпоследнем параграфе);
• в также распространённых базисах «И-НЕ» и «ИЛИ-НЕ» (в последнем параграфе).

Логические схемы строятся на основе логических выражений и функций. Бывает, что изначально составленная функция является излишне сложной, из-за чего её схемная или программная реализация оказывается избыточной. Способам и приёмам минимизации логических функций посвящены отдельные материалы сайта — минимизация логических функций: общие сведения, минимизация логических функций: метод непосредственных преобразований и минимизация логических функций: метод Квайна.

Задача анализа логических схем

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

1. Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
2. Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра — номер яруса, а остальные цифры — порядковый номер элемента в ярусе.
3. Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
4. Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.

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

Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x, y, z :

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

.

Таблица истинности для данной логической схемы:

x	y	z					f
1	1	1	0	1	1	1	1
1	1	0	0	0	0	1	0
1	0	1	0	0	0	1	0
1	0	0	0	0	0	1	0
0	1	1	0	0	0	1	0
0	1	0	0	0	0	1	0
0	0	1	0	0	0	1	0
0	0	0	1	0	1	0	0

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

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

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

Продолжаем искать булеву функцию логической схемы вместе

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

Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x, y, z :

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

.

Таблица истинности для данной логической схемы:

x	y	z			f
1	1	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
1	0	0	0	0	0
0	1	1	0	1	1
0	1	0	0	1	1
0	0	1	0	1	1
0	0	0	0	1	1

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

Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная — самая нижняя — пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x, y, z :

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

.

Таблица истинности для данной логической схемы:

x	y	z			f
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	0	1
0	0	0	1	0	1

Задача синтеза логических схем в булевом базисе

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

Каждой дизъюнкции (логической сумме) соответствует элемент «ИЛИ», число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент «И», число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент «НЕ».

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

Пример 6. Построить логическую схему, реализующую функцию с данной таблицей истинности:

Решение. Разбираем таблицу истинности для логической схемы. Определяем функцию, которая получится на выходе схемы и промежуточные функции, которые на входе принимают аргументы x и y . В первой строке результатом реализации выходной функции при том, что значения входных переменных равны единицам, должен быть логический «0», во второй строке — при разных значениях входных переменных на выходе тоже должен быть логический «0». Поэтому нужно, чтобы выходная функция была конъюнкцией (логическим произведением).

Теперь подбираем промежуточные функции. Получаем следующую таблицу для промежуточных функций и выходной функции — конъюнкции промежуточных функций:

0	0	0
0	1	0
1	1	1
0	1	0

Для построения логической схемы необходимо элементы, реализующие логические операции, указанные в выходной функции, располагать в порядке, заданной этой функцией. Из выражения видно, что понадобятся 3 схемы «НЕ», две двухвходовых схемы «И» и одна двухвходовая схема «ИЛИ». В соответствии с выходной функцией получаем следующую логическую схему:

А теперь очередь дошла до функций алгебры логики четырёх переменных. Сначала выполним синтез логической схемы в булевом базисе.

Пример 7. Построить в булевом базисе логическую схему, реализующую функцию алгебры логики

Решение. Для построения логической схемы потребуются 4 схемы «НЕ», одна трёхвходовая схема «И», 2 двухвходовые схемы «И» и одна трёхвходовая схема «ИЛИ». В соответствии с этим получаем следующую логическую схему:

Задача синтеза логических схем в базисах «И-НЕ» и «ИЛИ-НЕ»

Часто для сокращения числа микросхем используют элементы «И-НЕ» или/и «ИЛИ-НЕ». Рассмтрим примеры, как построить схему, реализующую ту же функцию, что в предыдущем примере, но, сначала в базисе «И-НЕ», а затем в базисе «ИЛИ-НЕ».

Пример 8. Построить в базисе «И-НЕ» логическую схему, реализующую функцию алгебры логики .

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

Для построения логической схемы потребуются 8 схем «И-НЕ». Получаем следующую логическую схему:

Пример 9. Построить в базисе «ИЛИ-НЕ» логическую схему, реализующую функцию алгебры логики .

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

Теория к заданию 2 из ЕГЭ по информатике

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

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

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

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

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

Кроме двузначной алгебры высказываний, в которой принимаются только два значения — «истинно» и «ложно», существует многозначная алгебра высказываний. В такой алгебре, кроме значений «истинно» и «ложно», употребляются такие истинностные значения, как «вероятно», «возможно», «невозможно» и т. д.

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖<->$) или такими условными обозначениями, как ¬, ‘not’, и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖<->$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

Операция, используемая относительно одной величины, называется унарной. Таблица значений данной операции имеет вид

Высказывание $A↖<->$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖<->$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если. то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина.

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

Операция эквивалентности противоположна сложению по модулю два и имеет результат «истина» тогда и только тогда, когда значения переменных совпадают.

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

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

С помощью логических переменных и логических операций любое логическое высказывание можно формализовать, т. е. заменить логической формулой. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу, но это не мешает определять истинность или ложность составного высказывания. Например, высказывание «Если пять больше двух (А), то вторник всегда наступает после понедельника (В)» — импликация А → В, и результат операции в данном случае — «истина». В логических операциях смысл высказываний не учитывается, рассматривается только их истинность или ложность.

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X 3) ∨ (1 3) ∨ (12 3) ∨ (3 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Логические выражения и их преобразование

Под логическим выражением следует понимать такую запись, которая может принимать логическое значение «истина» или «ложь». При таком определении среди логических выражений необходимо различать:

• выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
• непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

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

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a — π/b) a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b a + a b > a + b, после подстановки получим: 3 2 + 2 3 > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b a + a b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

4) sin(π/a — π/b) =1» (значение дизъюнкции равно 1, если сумма двух операндов больше или равна 1). Знак «&» на схеме И является сокращенной записью английского слова and.

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

Построение таблиц истинности логических выражений

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

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы $↖ <->∧ X2 ∨ ↖ <->∨ X1$.

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.

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

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

Алгоритм построения ДНФ следующий:

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

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ $↖<->$ ∧ $↖<->$.

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

Алгоритм построения КНФ следующий:

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

Примеры решения задач

Пример 1. Рассмотрим предыдущий пример, т. е. построим функцию, определяющую, что первое число равно второму, используя метод КНФ. Для заданной функции ее таблица истинности имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 0. Это вторая и третья строки (строку заголовка при нумерации не учитываем).

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ $↖<->$ ∧ $↖<->$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ $↖<->$ ∧ $↖<->$ ∨ X2 = X1 ∧ $↖<->$ ∨ X1 ∧ X2 ∨ $↖<->$ ∧ $↖<->$ ∨ $↖<->$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $↖<->$ ∧ $↖<->$ ∨ 0 = X1 ∧ X2 ∨ $↖<->$ ∧ $↖<->$.

Пример 2. Построить логическую функцию для заданной таблицы истинности:

Решение. Используем алгоритм ДНФ для построения исходной функции:

Искомая формула: X1 ∧ X2 ∨ $↖<->$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ $↖<->$ ∧ X2 = X2 ∧ (X1 ∨ $↖<->$) = X2 ∧ 1 = X2.

Пример 3. Для приведенной таблицы истинности построить логическую функцию, используя метод ДНФ.

Искомая формула: X1 ∧ X2 ∧ X ∨ $↖<->$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $↖<->$ ∪ X1 ∧ $↖<->$ ∧ $↖<->$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ $↖<->$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $↖<->$ ∨ X1 ∧ $↖<->$ ∧ $↖<->$ = X2 ∧ X3 ∧ (X1 ∨ $↖<->$) ∨ X1 ∧ $↖<->$ ∧ (X2 ∨ $↖<->$) = X2 ∧ X3 ∨ X1 ∧ $↖<->$.

Таблицы истинности для решения логических задач

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

Примеры решения задач

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

Решение. Очевидно, что результатом решения будет таблица, в которой искомая функция Y(X1, X2, X3) будет иметь значение «истина», если какие-либо две переменные имеют значение «истина».

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

Из таблицы видно, что существуют два варианта искомого расписания:

1. математика, информатика, физика;
2. информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

1. Борис — самый старший;
2. играющий в футбол младше играющего в хоккей;
3. играющие в футбол и хоккей и Петр живут в одном доме;
4. когда между лыжником и теннисистом возникает ссора, Борис мирит их;
5. Петр не умеет играть ни в теннис, ни в бадминтон.

Какими видами спорта увлекается каждый из мальчиков?

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

Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.

Из условия 4 следует, что Борис не увлекается ни лыжами, ни теннисом, а из условий 3 и 5, что Петр не умеет играть в футбол, хоккей, теннис и бадминтон. Следовательно, любимые виды спорта Петра — лыжи и плавание. Занесем это в таблицу, а оставшиеся клетки столбцов «Лыжи» и «Плавание» заполним нулями.

Из таблицы видно, что в теннис может играть только Алексей.

Из условий 1 и 2 следует, что Борис не футболист. Таким образом, в футбол играет Алексей. Продолжим заполнять таблицу. Внесем в пустые ячейки строки «Алексей» нули.

Окончательно получаем, что Борис увлекается хоккеем и бадминтоном. Итоговая таблица будет выглядеть следующим образом:

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.