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

При составлении таблицы истинности для логического выражения необходимо:

Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных).

Выяснить количество столбцов (определяется как количество переменных + количество логических операций).

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

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

Заполнить таблицу истинности по столбцам.

Контрольный пример . Построить таблицу истинности для выражения F = (A V B) & (¬A V ¬B).

Количество строк в таблице определяется как 2 2 (2 переменных) + 1 (заголовок таблицы) = 5.

Количество столбцов – как 2 логические переменные (A, B) + 5 логических операций (&, V, ¬, →, ↔).

Расставим порядок выполнения операций:

(A V B) & (¬A V ¬B).

Построим таблицу истинности для данного логического выражения (таблица 5).

Таблица 5 – Таблица истинности для логического выражения

						(A V B) & (¬A V ¬B)

Контрольный пример . Построить таблицу истинности для логического выражения X V Y & ¬Z.

Количество строк = 2 3 + 1 = 9.

Количество столбцов = 3 логические переменные + 3 логических операций = 6.

Укажем порядок действий:

Нарисуем и заполним таблицу 6:

Таблица 6 – Таблица истинности для логического выражения

1.4 Построение логических схем

С точки зрения логики электрический ток либо течет, либо не течет; электрический импульс есть или нет; электрическое напряжение есть или нет. Рассмотрим электрические контактные схемы, реализующие логические операции (схемы 1 – 3). На схемах 1 – 3 контакты обозначены латинскими буквами A и B.

Схема 1 – Конъюнкция Схема 2 – Дизъюнкция Схема 3 – Инверсия

(автоматический ключ)

Схема 4 – Конъюнктор Схема 5 – Дизъюнктор Схема 6 – Инвертор

Цепь на схеме 1 с последовательным соединением контактов соответствует логической операции «И» и представляется конъюнктором (схема 4). Цепь на схеме 2 с параллельным соединением контактов соответствует логической операции «ИЛИ» и представляется дизъюнктором (схема 5). Цепь на схеме 3 (электромагнитное реле) соответствует логической операции «НЕ» и представляется инвертором (схема 6).

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

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

Правило построения логических схем:

Определить число логических переменных.

Определить количество базовых логических операций и их порядок.

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

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

Контрольный пример. Пусть X = Истина (1), Y = Ложь (0). Составьте логическую схему для следующего логического выражения: F = X V Y & X.

1) Две переменные –X и Y.

2) Две логические операции: X V Y & X.

3) Строим схему (рисунок 3).

4) Ответ: 1 V 0 & 1 = 1.

Рисунок 3 – Логическая схема для логического выражения F = X V Y & X

1. Определить порядок действий.

2. Определить размерность таблицы истинности.

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

4. Сформулировать ответ.
В последнем столбце один "0", соответствующий А, равному "1", и В, равному "0". Получается, что данная функция ложна тогда и только тогда, когда логическая переменная А истинна, а логическая переменная В ложна, что соответствует логической функции СЛЕДСТВИЕ.
Значит, данная функция равна логическому следствию переменных А и В: Если А, то В.

Составить таблицу истинности для логической функции:

1. Определить порядок действий.

2. Определить размерность таблицы истинности.

"Шапка" таблицы содержит две строки - номера действий и логические операции действий.
Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их пять).
Количестко строк в таблице равно двойке в степени, равной количеству логических переменных - в случае двух переменных получается 4 строки..
3. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.


4. Сформулировать ответ.
В последнем столбце "1", соответствуют А равному В, а "0" - А неравному В. Получается, что данная функция истинна, когда А равно В и ложна, когда А не равно В, что соответствует логической функции ТОЖДЕСТВО.
Значит, данная функция равна логическому ТОЖДЕСТВУ переменных А и В: А тождественно В.

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

Операнды в данном случае подаются - на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат по сути входными данными. Так, напряжение высокого уровня - это логическая единица 1 - обозначает истинное значение операнда, а напряжение низкого уровня 0 - значение ложное. 1 - ИСТИНА, 0 - ЛОЖЬ.

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

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

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

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

Логический элемент «И» - конъюнкция, логическое умножение, AND

«И» - логический элемент, выполняющий над входными данными операцию конъюнкции или логического умножения. Данный элемент может иметь от 2 до 8 (наиболее распространены в производстве элементы «И» с 2, 3, 4 и 8 входами) входов и один выход.

Условные обозначения логических элементов «И» с разным количеством входов приведены на рисунке. В тексте логический элемент «И» с тем или иным числом входов обозначается как «2И», «4И» и т. д. - элемент «И» с двумя входами, с четырьмя входами и т. д.

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

На западных схемах значок элемента «И» имеет прямую черту на входе и закругление на выходе. На отечественных схемах - прямоугольник с символом «&».

Логический элемент «ИЛИ» - дизъюнкция, логическое сложение, OR

«ИЛИ» - логический элемент, выполняющий над входными данными операцию дизъюнкции или логического сложения. Он так же как и элемент «И» выпускается с двумя, тремя, четырьмя и т. д. входами и с одним выходом. Условные обозначения логических элементов «ИЛИ» с различным количеством входов показаны на рисунке. Обозначаются данные элементы так: 2ИЛИ, 3ИЛИ, 4ИЛИ и т. д.

Таблица истинности для элемента «2ИЛИ» показывает, что для появления на выходе логической единицы, достаточно чтобы логическая единица была на первом входе ИЛИ на втором входе. Если логические единицы будут сразу на двух входах, на выходе также будет единица.

На западных схемах значок элемента «ИЛИ» имеет закругление на входе и закругление с заострением на выходе. На отечественных схемах - прямоугольник с символом «1».

Логический элемент «НЕ» - отрицание, инвертор, NOT

«НЕ» - логический элемент, выполняющий над входными данными операцию логического отрицания. Данный элемент, имеющий один выход и только один вход, называют еще инвертором, поскольку он на самом деле инвертирует (обращает) входной сигнал. На рисунке приведено условное обозначение логического элемента «НЕ».

Таблица истинности для инвертора показывает, что высокий потенциал на входе даёт низкий потенциал на выходе и наоборот.

На западных схемах значок элемента «НЕ» имеет форму треугольника с кружочком на выходе. На отечественных схемах - прямоугольник с символом «1», с кружком на выходе.

Логический элемент «И-НЕ» - конъюнкция (логическое умножение) с отрицанием, NAND

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

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

Логический элемент «ИЛИ-НЕ» - дизъюнкция (логическое сложение) с отрицанием, NOR

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

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

Логический элемент «исключающее ИЛИ» - сложение по модулю 2, XOR

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

Изображение в западных схемах - как у «ИЛИ» с дополнительной изогнутой полоской на стороне входа, в отечественной - как «ИЛИ», только вместо «1» будет написано «=1».

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

Определение 1

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

Определение 2

Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него.

Определение 3

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

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

Рисунок 1.

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

Алгоритм построения таблицы истинности логической функции

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

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

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

Рисунок 2.

Пример 1

Составить таблицу истинности логического выражения $D=\bar{A} \vee (B \vee C)$.

Решение:

Определим количество строк:

кол-во строк = $2^3 + 1=9$.

Количество переменных – $3$.

1. инверсия ($\bar{A}$);
2. дизъюнкция, т.к. она находится в скобках ($B \vee C$);

3. дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.

   Кол-во столбцов = $3 + 3=6$.

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

Рисунок 3.

Пример 2

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

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.

Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:

1. отрицание ($\bar{C}$);
2. дизъюнкция, т.к. она находится в скобках ($A \vee B$);
3. конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
4. отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
5. дизъюнкция ($A \vee C$);
6. конъюнкция ($(A\vee C)\bigwedge B$);
7. отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);

8. дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).

Продолжительность урока: 45 мин

Тип урока: комбинированный:

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

Цели урока:

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

План урока:

1. Организационный момент (2 мин).
2. Повторение материала предыдущего урока (устный опрос) (4 мин).
3. Объяснение нового материала (12 мин).
4. Закрепление

• разбор примера (5 мин);
• практические упражнения (10 мин);
• задания для самостоятельной работы (10 мин).

Обобщение урока, домашнее задание (2 мин).

Оборудование и программный материал:

• белая доска;
• мультимедийный проектор;
• компьютеры;
• редактор презентаций MS PowerPoint 2003;
• раздаточный справочный материал “Таблицы истинности”;
• демонстрация презентации “Таблицы истинности”.

Ход урока

I. Организационный момент

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

II. Повторение материала предыдущего урока

Давайте вспомним основные определения и понятия:

Вопрос	Ответ
1. Какое предложение является высказыванием?	Повествовательное предложение, в котором что-либо утверждается или отрицается
2. На какие виды делятся высказывания по своей структуре?	Простые и сложные
3. Истинность каких высказываний является договорной?	Простых
4. Истинность каких высказываний вычисляется?	Сложных
5. Как обозначаются простые высказывания в алгебре высказываний?	Логическими переменными
6. Как обозначается истинность таких высказываний?	1 и 0
7. Что связывает переменные в формулах алгебры высказываний?	Логические операции
8. Перечислите их.	Инверсия (отрицание) Конъюнкция (умножение) Дизъюнкция (сложение) Импликация (следование) Эквиваленция (равносильность)
9. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране)	Нет, неправильно поставлен знак
10. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране)	Да

III. Объяснение нового материала

Последние два примера относятся к сложным высказываниям. Как же определить истинность сложных высказываний?

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

Итак, тема урока ТАБЛИЦЫ ИСТИННОСТИ.

3.1) Определение. Таблица истинности – это таблица, показывающая истинность сложного высказывания при всех возможных значениях входящих переменных (Рисунок 1).

3.2) Разберем подробнее каждую логическую операцию в соответствии с ее определением:

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

Эта операция относится только к одной переменной, поэтому для нее отведено только две строки, т.к. одна переменная может иметь одно из двух значений: 0 или 1.

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

Легко увидеть, что данная таблица действительно похожа на таблицу умножения.

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

Можно убедиться, что таблица похожа на таблицу сложения кроме последнего действия. В двоичной системе счисления 1 + 1 = 10, в десятичной – 1 + 1 = 2. В логике значения переменной 2 невозможно, рассмотрим 10 с точки зрения логики: 1 – истинно, 0 – ложно, т.о. 10 – истинно и ложно одновременно, чего быть не может, поэтому последнее действие строго опирается на определение.

4. Импликация (следование) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие истинное, а следствие ложно.

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

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

3.3) Разберем алгоритм составления таблицы истинности для сложного высказывания:

3.4) Рассмотрим пример составления таблицы истинности для сложного высказывания:

Пример. Построить таблицу истинности для формулы: А U В -> ¬А U С.

Решение (Рисунок 2)

Из примера видно, что таблицей истинности является не все решение, а только последнее действие (столбец, выделенный красным цветом).

IV. Закрепление.

Для закрепления материала вам предлагается решить самостоятельно примеры под буквами а, б, в, дополнительно г–ж (Рисунок 3).

V. Домашнее задание, обобщение материала.

Домашнее задание дано вам также на экране монитора (Рисунок 4)

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