Таблица истины и лжи. I

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

Операнды в данном случае подаются - на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат по сути входными данными. Так, напряжение высокого уровня - это логическая единица 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. Разбить выражение на простые утверждения и обозначить каждое из них как переменную.
2. Определить логические преобразования.
3. Выявить порядок действий этих преобразований.
4. Сосчитать строки в будущей таблице. Их количество равно два в степени N, где N - число переменных, плюс одна строка для шапки таблицы.
5. Определить число столбцов. Оно равно сумме количества переменных и количества действий. Можно представлять результат каждого действия в виде новой переменной, если так будет понятней.
6. Шапка заполняется последовательно, сначала все переменные, потом результаты действий в порядке их выполнения.
7. Заполнение таблицы надо начать с первой переменной. Для неё количество строк делится пополам. Одна половина заполняется нулями, вторая - единицами.
8. Для каждой следующей переменной нули и единицы чередуются вдвое чаще.
9. Таким образом заполняются все столбцы с переменными и для последней переменной значение меняется в каждой строке.
10. Потом последовательно заполняются результаты всех действий.

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

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

1. выражения в скобках;
2. отрицание или инверсия;
3. конъюнкция;
4. строгая и обычная дизъюнкция;
5. импликация;
6. эквивалентность.

Примеры

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

• Штрих Шеффера.
• Стрелка Пирса.
• Определение эквивалентности.

Штрих Шеффера

Штрих Шеффера - это логическое выражение, которое можно записать в виде "не (А и Б)". Здесь две переменные, и два действия. Конъюнкция в скобках, значит, она выполняется первой. В таблице будет шапка и четыре строки со значениями переменных, а также четыре столбца. Заполним таблицу:

Отрицание конъюнкции выглядит как дизъюнкция отрицаний. Это можно проверить, если составить таблицу истинности для выражения "не А или не Б". Проделайте это самостоятельно и обратите внимание, что здесь будет уже три операции.

Стрелка Пирса

Рассматривая Стрелку Пирса, которая представляет собой отрицание дизъюнкции "не (А или Б)", сравним её с конъюнкцией отрицаний "не А и не Б". Заполним две таблицы:

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

Определение эквивалентности

Про утверждения А и Б можно сказать, что они эквивалентны, тогда и только тогда, когда из А следует Б и из Б следует А. Запишем это как логическое выражение и построим для него таблицу истинности. "(А эквивалентно Б) эквивалентно (из А следует Б) и (из Б следует А)".

Здесь две переменных и пять действий. Строим таблицу:

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

Абсолютно все цифровые микросхемы состоят из одних и тех же логических элементов – «кирпичиков» любого цифрового узла. Вот о них мы и поговорим сейчас.

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

Итак, какие бывают элементы?

Элемент «И» (AND)

Иначе его называют «конъюнктор».

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

Вот так выглядит элемент «И» и его таблица истинности:

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

Смотрим таблицу истинности, и проясняем в мозгу принцип. Понять его не сложно: единица на выходе элемента «И» возникает только тогда, когда на оба входа поданы единицы. Это объясняет название элемента: единицы должны быть И на одном, И на другом входе.

Если посмотреть чуток иначе, то можно сказать так: на выходе элемента «И» будет ноль в том случае, если хотя бы на один из его входов подан ноль. Запоминаем. Идем дальше.

Элемент «ИЛИ» (OR)

По другому, его зовут «дизъюнктор».

Любуемся:

Опять же, название говорит само за себя.

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

Элемент «НЕ» (NOT)

Чаще, его называют «инвертор».

Надо чего-нибудь говорить по поводу его работы?

Элемент «И-НЕ» (NAND)

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

Элемент «ИЛИ-НЕ» (NOR)

Та же история – элемент «ИЛИ» с инвертором на выходе.

Следующий товарищ устроен несколько хитрее:
Элемент «Исключающее ИЛИ» (XOR)

Он вот такой:

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

Смотрим таблицу истинности. Когда на выходе единицы? Правильно: когда на входах разные сигналы. На одном – 1, на другом – 0. Вот такой он хитрый.

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

Ее запоминать не обязательно.

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

Ну и напоследок – несколько микросхем, внутри которых содержатся цифровые элементы. Около выводов элементов обозначены номера соответствующих ног микросхемы. Все микросхемы, перечисленные здесь, имеют 14 ног. Питание подается на ножки 7 (-) и 14 (+). Напряжение питания – смотри в таблице в предыдущем параграфе.

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль . Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b) .

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

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

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквивалентность.

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

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

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

Алгоритм построения таблиц истинности для сложных выражений:

количество строк = 2 n + строка для заголовка ,

n - количество простых высказываний.

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

o определить количество переменных (простых выражений);

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

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

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

D = А & (B  C) .

Решение: 

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 2 3 +1 = 9.

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

o простые выражения (переменные): А, В, С ;

o промежуточные результаты (логические операции):

o А - инверсия (обозначим через E );

o B  C - операция дизъюнкции (обозначим через F );

o а также искомое окончательное значение арифметического выражения:

o D = А & (B  C) . т.е. D = E & F - это операция конъюнкции.

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

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

Правила построения логической функции по ее таблице истинности:

1. Выделить в таблице истинности те строки, в которых значение функции равно 1 .

2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.

3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.

4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0 , то этот аргумент взять с отрицанием.

Решение.

1. В первой и третьей строках таблицы истинности значение функции равно 1 .

2. Так как строки две, получаем дизъюнкцию двух элементов: () V () .

3. Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y : (X & Y) V (X & Y) .

4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию:

5. Z (X, Y) =(X & Y) V (X & Y) .

Пример 4. Определить участника преступления, исходя из двух посылок:

1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";

2) 2) "Если Иванов не участвовал, то Сидоров не участвовал".

Решение

Составим выражения:

I - "Иванов участвовал в преступлении";

P - "Петров участвовал в преступлении";

S - "Сидоров участвовал в преступлении".

Запишем посылки в виде формул:

Проверим результат, используя таблицу истинности:

Ответ: Иванов участвовал в преступлении.

Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов Q=2 3 =8 .

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

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

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

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

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

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

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

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


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