12.3.4. Логические объекты-функции Логические объекты-функции поддерживают операции "логическое И" (возвращает true, если оба операнда равны true, – применяет оператор &&, аcсоциированный с типом Type), "логическое ИЛИ" (возвращает true, если хотя бы один из операндов равен true, –

Логические операции К логическим относятся бинарные операции and, or и xor, а также унарная операция not, имеющие операнды типа boolean и возвращающие значение типа boolean. Эти операции подчиняются стандартным правилам логики: a and b истинно только тогда, когда истинны a и b, a or b истинно

В выражении. Для n логических переменных понадобится 2^n строк таблицы истинности , не считая строки с заголовками. Затем посчитайте количество логических операций в выражении. Столбцов в таблице будет столько же, операций плюс n столбцов для переменных.
Пусть дано выражение с тремя , записанное на рисунке. Переменных три, поэтому строк потребуется 8. Количество операций - 3, поэтому число столбцов с учетом переменных 6. Начертите таблицу и заполните ее заголовок.

Теперь заполните столбцы, надписанные переменными, всеми возможными вариантами переменных. Чтобы не пропустить ни одного варианта, удобно представить для себя эти последовательности нулей и единиц в виде от 0 до 2^n. Для трех переменных это двоичные числа от 0 до 8 или от 000 до 111 в двоичной .

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

Видео по теме

Источники:

• Таблицы истинности

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

Инструкция

Таблица истинности для сложного строится по следующему алгоритму:
1. Определяется количество по формуле
количество строк = 2^n + строка для заголовка, где n – количество простых высказываний,
2. Определяется количество столбцов по формуле
количество столбцов = количество переменных + количество логических операций,
3. Строится и

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

Логические переменные изучаются в специальном разделе математики, который носит название алгебры логики (высказываний), или булевой алгебры. Булева алгебра названа по имени английского математика Джорджа Буля (1815–1864), внесшего значительный вклад в разработку алгебры логики. Предметом изучения алгебры логики являются высказывания, при этом анализу подвергается истинность или ложность высказываний, а не их смысловое содержание. Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами: А, В, С, D, … и т. д. Составные высказывания на естественном языке образуются с помощью союзов. В алгебре логики эти союзы заменяются логическими операциями. В соответствии с алгеброй логики любое составное высказывание можно рассматривать как логическую функцию F(А, В, С, …), аргументами которой являются логические переменные А, В, С… (простые высказывания). Логические функции и логические переменные (аргументы) принимают только два значения: «истина», которая обозначается логической единицей – 1 и «ложь», обозначаемая логическим нулем – 0. Логическую функцию называют также предикатом.

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

1. Логическая операция ИНВЕРСИЯ (отрицание). В естественных языках соответствует словам неверно, ложь или частице не, Not, в алгебре логики обозначается

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

Математическая запись данной операции для логической переменной А будет иметь вид:

2. Логическая операция КОНЪЮНКЦИЯ (логическое умножение). В естественных языках соответствует союзу и, в языках программирования обозначается And, в алгебре логики обозначается & .

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

Д В, С, … будет иметь вид:

F = A & B & C & …

3. Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение). В естественных языках соответствует союзу или, в языках программирования обозначается Or, в алгебре логики обозначается V.

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

Математическая запись данной операции для логических переменных A, В, С, … будет иметь вид:

F = AvBvC…

4. Логическая операция ИМПЛИКАЦИЯ (логическое следование). В естественных языках соответствует обороту речи, если…, то …, в языках программирования обозначается If,

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

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

F = A?B.

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

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

Математическая запись данной операции для логических переменных A, В, С… будет иметь вид:

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

Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.

1. Закон противоречия:

2. Закон исключенного третьего:

3. Закон двойного отрицания:

4. Законы де Моргана:

5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.

6. Законы поглощения: A ? (A & B) = A; A & (A ? B) = A.

7. Законы исключения констант: A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B & 1 = B; B & 0 = 0.

8. Законы склеивания:

9. Закон контрапозиции: (A ? B) = (B ? A).

Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:

1. Коммутативный закон: A & B = B & A; A ? B = B ? A.

2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C.

3. Дистрибутивный закон: A & (B ? C) = (A & B) ? (A & C).

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

Выполним преобразование, например, логической функции

применив соответствующие законы алгебры логики.

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

Например, для логической функции F = A v B v C (дизъюнкции) трех логических переменных А, В, и С таблица истинности будет иметь вид, показанный на рис. 4.1. Для записи значений логических переменных и логической функции данная таблица истинности содержит 8 строк и 4 столбца, т. е. число строк для записи значений аргументов и функции любой таблицы истинности будет равно 2 n , где п – число аргументов логической функции, а число столбцов равно п + 1.

Рис. 4.1. Таблица истинности для логической функции F = A v В v С

Таблицу истинности можно составить для любой логической функции, например, на рис. 4.2 приведена таблица истинности логической функции F = A ? B ? C (эквиваленции).

Логические функции имеют соответствующие названия. Для двух двоичных переменных существует шестнадцать логических функций, названия которых приведены ниже. На рис. 4.3 представлена таблица, в которой приведены логические функции F 1 , F 2 , F 3 , … , F 16 двух логических переменных A и В.

Функция F 1 = 0 и называется функцией константы нуля, или генератора нуля.

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

Рис. 4.3. Логические функции F 1 , F 2 , F 3 ,… F 16 двух аргументов А и В

Функция F 2 = A & B называется функцией конъюнкции.

А.

Функция F 4 = А А.

называется функцией запрета по логической переменной В.

Функция F 6 = В называется функцией повторения по логической переменной В.

называется функцией исключающее «ИЛИ».

Функция F 8 = A v В называется функцией дизъюнкции.

называется функцией Пирса.

называется функцией эквиваленции.

В.

Функция F 12 = B ? A B ? A.

называется функцией отрицания (инверсии) по логической переменной А.

Функция F 14 = A ? B называется функцией импликации A ? B .

называется функцией Шеффера.

Функция F 16 = 1 называется функцией генератора 1.

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

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

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

Рис. 4.4. Диалоговое окно «Мастер функций – шаг 1 из 2»

Как видно из рис. 4.4, в состав логических функций программы MS Excel входит функционально полный набор логических функций, состоящий из следующих логических функций: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание). Таким образом, с помощью функционально полного набора логических функций программы MS Excel можно реализовать другие функции. Логическая функция ЕСЛИ (импликация), также входящая в логические функции MS Excel, выполняет логическую проверку и в зависимости от результата проверки выполняет одно из двух возможных действий. В данной программе она имеет следующий формат: = ЕСЛИ (арг1;арг2;арг3), где арг1 – логическое условие; арг2 – возвращаемое значение при условии, что значение аргумента арг1 выполняется (ИСТИНА); арг3 – возвращаемое значение при условии, что значение аргумента арг1 не выполняется (ЛОЖЬ). Например, если в произвольную ячейку листа программы MS Excel ввести выражение « = ЕСЛИ (А1 = 5; „пять“; „не пять“)», то при вводе числа 5 в ячейку А1 и нажатии клавиши «Enter» в ячейке А1 автоматически будет записано слово «пять», при вводе любого другого числа в ячейку А1 в ней запишется слово «не пять». Как уже отмечалось, с помощью логических функций программы MS Excel можно представить другие логические функции и соответствующие им таблицы истинности.

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

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

Сложные цифровые логические устройства, входящие в состав компьютера, состоят из ряда элементарных логических элементов, построенных на базе средств электронной техники. При производстве этих электронных логических элементов используют различные технологии и схемотехнические решения, такие как: ДТЛ (диодно-транзисторная логика), ТТЛ (транзисторно-транзисторная логика), ЭСЛ (эмиттерно-связанная логика), технологии, основанные на использовании полевых транзисторов, и т. д. Логические элементы позволяют реализовать любую логическую функцию. Входные и выходные сигналы логических элементов, соответствующие двум логическим состояниям 1 и 0, могут иметь один из двух установленных уровней электрического напряжения, который зависит от схемотехнического решения логического элемента. Например, для логических элементов, основанных на технологии ТТЛ, высокий уровень электрического напряжения (2,4 ? 5 В) соответствует значению логической единицы (истина), а низкий уровень (0 ? 0,4 В) – логическому нулю (ложь).

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

1. Логический элемент НЕ, который называется также инвертором, выполняет логическую операцию отрицания (инверсии).

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

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

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

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

Минтермом называют логическую функцию, которая принимает значение логической единицы только при одном значении логических переменных и значение логического нуля при других значениях логических переменных. Например, минтермами являются логические функции F 2 , F 3 , F 5 и F 9 (см. рис. 4.3).

Макстерном называют логическую функцию, которая принимает значение логического нуля только при одном значении логических переменных и значение логической единицы при других значениях логических переменных. Например, макстернами являются логические функции F 8 , F 12 , F 14 и F 15 (см. рис. 4.3).

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

Рассмотрим задачу синтеза на примере модифицированной таблицы истинности, приведенной на рис. 4.6. Для данной таблицы истинности необходимо записать выражение для выходной функции F, провести ее преобразование (минимизацию) на основе законов алгебры логики и, используя основные логические элементы – НЕ, И и ИЛИ, разработать логическую схему реализации выходной функции F.

Рис. 4.6. Таблица истинности логических переменных A, В и С

Значения логических переменных А, В и С и соответствующие значения функции F приведены в таблице истинности (см. рис. 4.6), где в столбце № – указан номер комбинации логических переменных A, В и С.

Для решения указанной задачи представим логическую функцию F в виде СДНФ, а затем и в СКНФ. Найдем вспомогательные функции минтермы и макстермы. В заданной таблице истинности выходная функция F принимает логическое значение, равное логической единице, при комбинациях логических переменных A, В и С , указанных под номерами 3, 6, 8, а значение, равное логическому нулю – при комбинациях, указанных под номерами 1, 2, 4, 5,7.

Минтермы запишем в следующем виде:

Минтермы представляют собой логические произведения (конъюнкции) логических переменных А, В, и С F, равных логической единице (комбинации 3, 6, 8). Сомножители (логические переменные A, В и С ) входят в минтерм в прямом виде (без отрицания), если их значения равны логической единице, и в инверсном (с отрицанием), если их значения равны логическому нулю. Логическая функция F в СДНФ будет равна логической сумме минтермов:

После минимизации логической функции Fc использованием законов алгебры логики получим ее искомое выражение:

Макстермы запишем в следующем виде:

Макстермы представляют собой логические суммы (дизъюнкции) логических переменных А, В, и С при значениях логической функции F, равных логическому нулю (комбинации 1, 2, 4, 5, 7). Слагаемые (логические переменные A, В, и С) входят в макстерм в прямом виде (без отрицания), если их значения равны логическому нулю, и в инверсном (с отрицанием), если их значения равны логической единице. Логическая функция F в С КНФ будет равна логическому произведению макстермов:

Поскольку полученное выражение для F в виде СКНФ является более громоздким по сравнению с представлением F в виде СДНФ, то в качестве окончательного выражения для F примем ее выражение в виде СДНФ, т. е.

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

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

Рис. 4.7. Реализация функции F в виде логической схемы

Для графического отображения логических схем существуют различные компьютерные программы, называемые графическими редакторами. Данные программы могут быть включены в другие компьютерные программы, например в программах Microsoft Word и Microsoft Excel такие редакторы реализованы с помощью панелей инструментов «Рисование», или быть самостоятельными программами, например Paint, Microsoft Visio и т. д. Воспользуемся встроенным графическим редактором (панель «Рисование») программы MS Excel для графического отображения логической схемы функции F. Данная логическая схема показана на рис. 4.8.

Рис. 4.8. Графическое отображение логической функции F с помощью программы MS Excel

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

Рассмотренные выше таблицы истинности логических элементов показывают установившиеся значения логических переменных. Однако когда логические переменные представлены в виде электрических сигналов, то необходимо некоторое время для того, чтобы значение логической функции достигло уровня установившегося состояния из-за внутренних задержек по времени в электронных логических элементах. В среднем задержка электрического сигнала такого элемента составляет 10 -9 с. В компьютере двоичные сигналы проходят через множество электронных схем, и задержка по времени может стать значительной. В этом случае выделяется отрезок времени (такт) на каждый шаг логической операции. Если операция заканчивается раньше, чем заканчивается тактовое время, то устройство, входящее в состав компьютера, ожидает ее окончания. В результате скорость выполнения операций несколько снижается, но достигается высокая надежность, так как обеспечивается синхронизация между многими параллельно выполняющимися операциями в компьютере. Синхронизация устройств в компьютере обеспечивается с помощью специального генератора – генератора тактовой частоты, который вырабатывает электрические импульсы стабильной частоты.

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

а) 101 и 110; б) 10101 и 11100; в) 110011 и 111100.

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

3. Доказать, что число логических функций двух логических переменных равно 16.

4. Реализовать модифицированные таблицы истинности логических схем НЕ, ИЛИ, И-НЕ, ИЛИ-НЕ (см. рис. 4.5), используя программу MS Excel.

5. Составить таблицы истинности для следующих логических функций:

6. Записать выражения для логических функций F 1 и F 2 в виде СДНФ и СКНФ. Логические функции F 1 и F 2 представлены далее соответственно таблицами истинности.

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

Инструкция . При вводе с клавиатуры используйте следующие обозначения:

Правила ввода логической функции

1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
По алгебраической форме можно построить схему логического устройства, используя логические элементы.


Рисунок1- Схема логического устройства

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

Операция НЕ - логическое отрицание (инверсия)

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Операция И - логическое умножение (конъюнкция)

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Приоритет логических операций

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация (→)
• Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Совершенная конъюнктивная нормальная форма

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

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

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

Алгебра логики (англ. 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)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

Отсюда получаем:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 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) < 1 ∧ ¬B ∧ ¬(b^a + 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 = sin(π/2 - π/3) < 1 = истина.

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

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

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

Тождественные преобразования логических выражений

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

Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.

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

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

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

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

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

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Ответ: A ∧ B ∧ ¬C.

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35

Решение. Запишем таблицу истинности для операции импликации:

Выражение X < (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Ответ: X = 5.

Использование логических выражений для описания геометрических областей

Логические выражения могут быть использованы для описания геометрических областей. В этом случае задача формулируется так: записать для заданной геометрической области такое логическое выражение, которое принимает значение «истина» для значений x, y тогда и только тогда, когда любая точка с координатами (x; y) принадлежит геометрической области.

Рассмотрим описание геометрической области с помощью логического выражения на примерах.

Пример 1. Задано изображение геометрической области. Записать логическое выражение, описывающее множество точек, принадлежащих ей.

1) .

Решение. Заданную геометрическую область можно представить в виде набора следующих областей: первая область — D1 — полуплоскость ${x}/{-1} +{y}/{1} ≤ 1$, вторая — D2 — круг с центром в начале координат $x^2 + y^2 ≤ 1$. Их пересечение D1 $∩$ D2 представляет собой искомую область.

Результат: логическое выражение ${x}/{-1}+{y}/{1} ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Эту область можно записать так: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

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

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

Пример 2. Нарисовать и заштриховать область, для точек которой выполняется логическое условие y ≥ x ∧ y + x ≥ 0 ∧ y < 2 .

Решение. Искомая область представляет собой пересечение трех полуплоскостей. Строим на плоскости (x, y) прямые y = x; y = -x; y = 2. Это границы области, причем последняя граница y = 2 не принадлежит области, поэтому ее наносим пунктирной линией. Для выполнения неравенства y ≥ x нужно, чтобы точки находились слева от прямой y = x, а неравенство y = -x выполняется для точек, которые находятся справа от прямой y = -x. Условие y < 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Использование логических функций для описания электрических схем

Логические функции очень удобны для описания работы электрических схем. Так, для схемы, представленной на рис., где значение переменной X — это состояние выключателя (если он включен, значение X — «истина», а если выключен — «ложь»), это значение Y — это состояние лампочки (если она горит — значение «истина», а если нет — «ложь»), логическая функция запишется так: Y = X . Функцию Y называют функцией проводимости.

Для схемы, представленной на рис., логическая функция Y имеет вид: Y = X1 ∪ X2, т. к. достаточно одного включенного выключателя, чтобы горела лампочка. В схеме на рис., для того чтобы горела лампочка, должны быть включены оба выключателя, следовательно, функция проводимости имеет вид: Y = X1 ∧ X2 .

Для более сложной схемы функция проводимости будет иметь вид: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

Использование аппарата алгебры логики при проектировании логических схем

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

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

Технически компьютерный логический элемент реализуется в виде электрической схемы, которая представляет собой соединение различных деталей: диодов, транзисторов, резисторов, конденсаторов. На вход логического элемента, который называют также вентилем, поступают электрические сигналы высокого и низкого уровней напряжения, на выход выдается один выходной сигнал также либо высокого, либо низкого уровня. Эти уровни соответствуют одному из состояний двоичной системы: 1 — 0; ИСТИНА — ЛОЖЬ. Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем. Работу логических схем описывают с помощью таблиц истинности. Условное обозначение на схеме ИЛИ знак «1» — от устаревшего обозначения дизъюнкции как «>=1» (значение дизъюнкции равно 1, если сумма двух операндов больше или равна 1). Знак «&» на схеме И является сокращенной записью английского слова and.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: F(X1, X2) = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

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

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

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

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

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

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

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

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

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

Ответ: X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

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

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

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

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

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

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

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

X1 ∧ X2 ∧ X3 ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∨ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$ = X2 ∧ X3 ∧ (X1 ∨ ${X1}↖{-}$) ∨ X1 ∧ ${X3}↖{-}$ ∧ (X2 ∨ ${X2}↖{-}$) = X2 ∧ X3 ∨ X1 ∧ ${X3}↖{-}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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