Таблица истинности - truth table

Логические выражения и таблица истинности

Примеры задач с решениями по этой теме Пройти тестирование по теме Контрольная по теме

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

Логическое выражение — составные высказывания в виде формулы.

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

Алгоритм построения таблицы истинности:

1.подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2n, где n — количество переменных;

3. подсчитать количество логических операций в формуле;

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

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

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

Заполнение таблицы:

1.разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2.разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

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

Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 23 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Пример 2. Определите истинность логического выражения F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2. m_строк=2n, m=22=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

А	В	А\/ В	¬А	¬В	¬А\/¬В	F
1	1	1
1	1	1	1	1
1	1	1	1	1
1	1	1

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

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

F = (A\/ B) /\ ¬С

В данной функции три логические переменные – А, В, С
количество строк таблицы = 23 =8
В формуле 3 логические операции.
Расставляем порядок действий

1) А\/ В; 2) ¬С; 3) (AVB) /\ ¬С .

количество столбцов таблицы = 3 + 3 = 6

А	В	С	A\/B	¬С	(A\/B) /\ ¬С
1
1
1	1	1	1
1	1	1
1	1	1	1
1	1	1
1	1	1	1	1
1	1	1	1

Пример 4. Определите истинность формулы: F = ((С \/В) => В) /\ (А /\ В) => В.

Построим таблицу истинности этой формулы.

Ответ: формула является тождественно истинной.

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
1
1
1	1

Какое выражение соответствует F?

1) ¬X/\¬Y/\Z 2) ¬X\/¬Y\/Z 3) X\/Y\/¬Z 4) X\/Y\/Z

Решение (вариант 1, через таблицы истинности):

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

X	Y	Z	F	¬X	¬Y	¬Z	¬X/\¬Y/\Z	¬X\/¬Y\/Z	X\/Y\/¬Z	X\/Y\/Z
1	1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1	1

Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/¬Z. Следовательно, правильный ответ – 3.

Ответ: 3

Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

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

1)первое заданное выражение ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2)второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;

3)третье выражение X\/Y\/¬Z соответствует F при всех предложенных комбинациях X,Y и Z;

4)четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Ответ: 3

Законы алгебры логики

Исключение констант	\( 1 + A = 1 \)\( 0 ⋅ A = 0 \)\( 0 + A = A \)\( 1 ⋅ A = A \)
Идемпотентность	\( A + A = A \)\( A ⋅ A = A \)
Закон исключения третьего	\( A + \overline{A} = 1 \)
Закон непротиворечивости	\( A ⋅ \overline{A} = 0 \)
Закон отрицания	\( \overline{\overline{A}} = A \)
Закон коммутативности	\( A + B = B + A \)\( A ⋅ B = B ⋅ A \)
Закон ассоциативности	\( A + B + C = A + (B + C)\)\( A ⋅ B ⋅ C = A ⋅ (B ⋅ C)\)
Закон дистрибутивности	\( A ⋅ (B + C) = A ⋅ B + A ⋅ C \)\( A + (B ⋅ C) = (A + B) ⋅ (A + C) \)
Правило де Моргана	\( \overline{(A + B)} = \overline{A} ⋅ \overline{B}\)\( \overline{(A ⋅ B)} = \overline{A} + \overline{B}\)
Закон поглощения	\( A + A ⋅ B = A\)\( A ⋅ (A + B) = A\)
Закон склеивания	\( A ⋅ B + \overline{A} ⋅ B = B \)\( (A + B) ⋅ (\overline{A} + B) = B \)

Законы алгебры можно доказать составив таблицу истинности.

^ (Исключающее ИЛИ)

Выполняет операцию «Исключающее ИЛИ» над каждой парой бит.

Исключающее ИЛИ равно 1, если только или только , но не оба одновременно .

Таблица истинности для исключающего ИЛИ:

Как видно, оно даёт 1, если ЛИБО слева , ЛИБО справа , но не одновременно. Поэтому его и называют «исключающее ИЛИ».

Пример:

Исключающее ИЛИ в шифровании

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

Иначе говоря, верна формула: .

Пусть Вася хочет передать Пете секретную информацию . Эта информация заранее превращена в число, например строка интерпретируется как последовательность кодов символов.

Вася и Петя заранее договариваются о числовом ключе шифрования .

Алгоритм:

Вася берёт двоичное представление и делает операцию . При необходимости бьётся на части, равные по длине , чтобы можно было провести побитовое ИЛИ для каждой части. В JavaScript оператор работает с 32-битными целыми числами, так что нужно разбить на последовательность таких чисел.
Результат отправляется Пете, это шифровка.

Например, пусть в очередное число равно , а ключ равен .

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

В нашем случае:

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

А где же побитовое исключающее ИЛИ (XOR)?

Побитовое исключающее ИЛИ (XOR) — это логический оператор, который используется в некоторых языках программирования для проверки на истинность нечётного количества условий.

Побитовое исключающее ИЛИ (XOR)
Левый операнд	Правый операнд	Результат
false	false	false
false	true	true
true	false	true
true	true	false

В языке C++ нет такого оператора. В отличии от логических И/ИЛИ, к XOR не применяется короткий цикл вычислений. Однако его легко можно сымитировать, используя оператор неравенства ():

if (a != b) … // a XOR b (предполагается, что a и b имеют тип bool)

1	if(a!=b)…// a XOR b (предполагается, что a и b имеют тип bool)

Можно также расширить количество операндов:

if (a != b != c != d) … // a XOR b XOR c XOR d (предполагается, что a, b, c и d имеют тип bool)

1	if(a!=b!=c!=d)…// a XOR b XOR c XOR d (предполагается, что a, b, c и d имеют тип bool)

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

Форма XOR, которая работает и с другими типами данных (с помощью оператора static_cast мы можем конвертировать любой тип данных в тип bool):

if (static_cast<bool>(a) != static_cast<bool>(b) != static_cast<bool>(c) != static_cast<bool>(d)) … // a XOR b XOR c XOR d, для любого типа, который может быть конвертирован в тип bool

1	if(static_cast<bool>(a)!=static_cast<bool>(b)!=static_cast<bool>(c)!=static_cast<bool>(d))…// a XOR b XOR c XOR d, для любого типа, который может быть конвертирован в тип bool

Сдвиг битов вправо с заполнением нулями (>>>)

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

В следующем примере выполняется сдвиг битов вправо на 2 разряда для чисел 9 и -9:

Выполнить код »
Скрыть результаты

При сдвиге вправо с заполнением нулями отрицательное число в двоичном формате обрабатывается как положительное число. Учитывая, что отрицательное число является дополнением его абсолютного значения до двух, число становится очень большим, например, результатом -9 >>> 2 будет 1073741821 в десятичном формате.

Символы

Есть три схематических символа для вентилей XOR: традиционные символы ANSI и DIN и символ IEC . В некоторых случаях символ DIN используется с ⊕ вместо ≢. Для получения дополнительной информации см. .


Условное обозначение ANSI XOR		Схематическое обозначение IEC XOR		Схематическое обозначение DIN XOR

В логические символы ⊕, J рд , и ⊻ может быть использован для обозначения операции XOR в алгебраических выражений.

C-подобные языки используют символ ^ для обозначения побитового XOR

(Обратите внимание, что каретка не обозначает логическое соединение (И) в этих языках, несмотря на сходство символа.)

Алгоритм

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

X := X XOR Y; /* XOR the values and store the result in X */
Y := Y XOR X; /* XOR the values and store the result in Y */
X := X XOR Y; /* XOR the values and store the result in X */

Поскольку XOR — это коммутативная операция , X XOR Y или Y XOR X могут использоваться взаимозаменяемо в любой из трех предыдущих строк; однако, когда замена с тремя XOR кодируется на языке ассемблера, эта взаимозаменяемость недоступна в каждой отдельной строке, потому что первый операнд инструкции XOR указывает целевое расположение, в котором сохраняется результат операции. Алгоритм обычно соответствует трем инструкциям машинного кода , представленным соответствующим псевдокодом и инструкциями сборки в трех строках следующей таблицы:

Псевдокод	Сборка IBM System / 370	сборка x86

В приведенном выше примере кода сборки System / 370 R1 и R2 — разные регистры , и каждая операция оставляет свой результат в регистре, указанном в первом аргументе. При использовании сборки x86 значения X и Y находятся в регистрах eax и ebx (соответственно), а результат операции помещается в первый регистр.

Однако в псевдокоде или версии или реализации на языке высокого уровня алгоритм не работает, если x и y используют одно и то же место хранения, поскольку значение, хранящееся в этом месте, будет обнулено первой инструкцией XOR, а затем останется нулевым; он не будет «заменен самим собой». Это не то же самое, что если бы x и y имели одинаковые значения. Проблема возникает только тогда, когда x и y используют одно и то же место хранения, и в этом случае их значения уже должны быть равны. То есть, если x и y используют одно и то же место хранения, тогда строка:

X := X XOR Y

устанавливает x равным нулю (потому что x = y, поэтому X XOR Y равно нулю) и устанавливает y равным нулю (поскольку он использует то же место хранения), в результате чего x и y теряют свои исходные значения.

Логические операторы

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

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

В языке C++ есть 3 логических оператора:

Оператор	Символ	Пример	Операция
Логическое НЕ	!	!x	true, если x — false и false, если x — true
Логическое И	&&	x && y	true, если x и y — true, в противном случае — false
Логическое ИЛИ	\|\|	x \|\| y	true, если x или y — true, в противном случае — false

Сдвиг битов вправо с сохранением знака (>>)

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

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

В следующем примере выполняется сдвиг битов вправо на 2 разряда для чисел 9 и -9:

Выполнить код »
Скрыть результаты

Побитовый сдвиг вправо на N позиций эквивалентен делению этого числа на 2N. Побитовый сдвиг выполняется намного быстрее обычного деления.

Ссылки [ править ]

Enderton , 2001
Эмиль Пост (июль 1921 г.). «Введение в общую теорию элементарных предложений». Американский журнал математики . 43 (3): 163–185. DOI . hdl . JSTOR .
^ Анеллис, Ирвинг Х. (2012). «Функциональный анализ Пирса и происхождение таблицы истины». История и философия логики . 33 : 87–97. DOI .
^

Процитированные работы править

Бохенский, Юзеф Мария (1959), Краткое изложение математической логики , перевод с французского и немецкого изданий Отто Берда, Дордрехт, Южная Голландия: Д. Рейдел.
Эндертон, Х. (2001). Математическое введение в логику , второе издание, Нью-Йорк: Harcourt Academic Press. ISBN 0-12-238452-0
Куайн, WV (1982), Методы логики , 4-е издание, Кембридж, Массачусетс: Издательство Гарвардского университета.

Отношение к современной алгебре

Хотя операторы ( конъюнкция ) и ( дизъюнкция ) очень полезны в логических системах, они не позволяют получить более обобщаемую структуру следующим образом:
∧{\ Displaystyle \ клин}∨{\ Displaystyle \ lor}

Системы и являются моноидами , но ни одна из них не является группой . К сожалению, это препятствует объединению этих двух систем в более крупные структуры, такие как математическое кольцо .
({Т,F},∧){\ Displaystyle (\ {Т, F \}, \ клин)}({Т,F},∨){\ Displaystyle (\ {T, F \}, \ lor)}

Тем не менее, система , использующая исключающее или является абелева группа . Комбинация операторов и элементов over дает хорошо известное поле . Это поле может представлять любую логику, доступную с помощью системы, и имеет дополнительное преимущество арсенала инструментов алгебраического анализа для полей.
({Т,F},⊕){\ displaystyle (\ {T, F \}, \ oplus)} ∧{\ Displaystyle \ клин}⊕{\ displaystyle \ oplus}{Т,F}{\ displaystyle \ {T, F \}} F2{\ displaystyle F_ {2}}(∧,∨){\ Displaystyle (\ земля, \ лор)}

Более конкретно, если связать с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение и операцию «исключающее ИЛИ» как сложение :
F{\ displaystyle F}Т{\ displaystyle T}F2{\ displaystyle F_ {2}}F2{\ displaystyle F_ {2}}

рзнак равноп∧q⇔рзнак равноп⋅q(мод2)рзнак равноп⊕q⇔рзнак равноп+q(мод2){\ displaystyle {\ begin {matrix} r = p \ land q & \ Leftrightarrow & r = p \ cdot q {\ pmod {2}} \\ r = p \ oplus q & \ Leftrightarrow & r = p + q {\ pmod {2}} \\\ end {matrix}}}

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

Унарные операции [ править ]

Есть 4 унарные операции:

Всегда правда
Никогда не правда, унарная ложь
Унарная идентичность
Унарное отрицание

Выходное значение всегда истинно, независимо от входного значения p.

**Логическая истина**
п	Т
Т	Т
F	Т

Логическая ложь править

Выходное значение никогда не бывает истинным: то есть всегда ложно, независимо от входного значения p.

**Логическая ложь**
п	F
Т	F
F	F

Логическая идентичность править

Логическая идентичность — это операция над одним логическим значением p, для которого выходным значением остается p.

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

**Логическая идентичность**
п	п
Т	Т
F	F

Логическое отрицание править

Логическое отрицание — это операция над одним логическим значением , обычно значением предложения , которая производит значение true, если его операнд ложен, и значение false, если его операнд истинен.

Таблица истинности для НЕ p (также записываемая как ¬p , Np , Fpq или ~ p ) выглядит следующим образом:

**Логическое отрицание**
п	¬p
Т	F
F	Т

Список побитовых операторов

Поразрядные операторы
Оператор	Использование	Описание
Побитовое И (AND)		Возвращает 1 в тех позициях результата, в которых биты каждого из операндов равны 1.
Побитовое ИЛИ (OR)		Возвращает 1 в тех позициях результата, в которых бит хотя бы одного из операндов равен 1.
Побитовое исключающее ИЛИ (XOR)		Возвращает 1 в тех позициях результата, в которых бит только одного из операндов равен 1.
Побитовое НЕ (NOT)		Заменяет каждый бит операнда на противоположный.
Сдвиг влево		Сдвигает двоичное представление числа a на b разрядов влево заполняя освободившиеся справа разряды нулями.
Правый сдвиг, переносящий знак		Сдвигает двоичное представление а на b разрядов вправо, отбрасывая уходящие биты.
Правый сдвиг с заполнением нулями		Сдвигает двоичное представление числа a на b разрядов вправо. Освобождающиеся разряды заполняются нулями.

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

Битовые сдвиги

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

Битовая адресация

Если ширина регистра (часто 32 или даже 64) больше, чем количество бит (обычно 8) наименьшего адресуемого блока (атомарного элемента), часто называемого байтом, операции сдвига вызывают схему адресации от байтов к биты. Таким образом, ориентации «влево» и «вправо» взяты из стандартной записи чисел в нотации разряда, так что сдвиг влево увеличивается, а сдвиг вправо уменьшает значение числа — если сначала считываются левые цифры, это составляет прямую последовательность байтов . Не обращая внимания на граничные эффекты на обоих концах регистра, операции арифметического и логического сдвига ведут себя одинаково, а сдвиг на 8-битные позиции переносит битовый шаблон на 1-байтовую позицию следующим образом:

Приложения

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

**Логическая эквивалентность: (п⇒q)≡(¬п∨q){\ Displaystyle (п \ Rightarrow q) \ Equiv (\ lnot p \ lor q)}**
п{\ displaystyle p}	q{\ displaystyle q}	¬п{\ displaystyle \ lnot p}	¬п∨q{\ Displaystyle \ lnot p \ lor q}	п⇒q{\ displaystyle p \ Rightarrow q}
Т	Т	F	Т	Т
Т	F	F	F	F
F	Т	Т	Т	Т
F	F	Т	Т	Т

Это свидетельствует о том , что является логическим эквивалентом к .
п⇒q{\ displaystyle p \ Rightarrow q}¬п∨q{\ Displaystyle \ lnot p \ lor q}

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

Вот таблица истинности, которая дает определения 7 наиболее часто используемых из :

п	Q	п∧Q{\ displaystyle P \ land Q}	п∨Q{\ Displaystyle P \ lor Q}	п ∨_ Q{\ Displaystyle P \ {\ underline {\ lor}} \ Q}	п ∧_ Q{\ Displaystyle P \ {\ underline {\ land}} \ Q}	п⇒Q{\ Displaystyle P \ Rightarrow Q}	п⇐Q{\ Displaystyle P \ Leftarrow Q}	п⇔Q{\ displaystyle P \ Leftrightarrow Q}
Т	Т	Т	Т	F	Т	Т	Т	Т
Т	F	F	Т	Т	F	F	Т	F
F	Т	F	Т	Т	F	Т	F	F
F	F	F	F	F	Т	Т	Т	Т
п	Q	п∧Q{\ displaystyle P \ land Q}	п∨Q{\ Displaystyle P \ lor Q}	п ∨_ Q{\ Displaystyle P \ {\ underline {\ lor}} \ Q}	п ∧_ Q{\ Displaystyle P \ {\ underline {\ land}} \ Q}	п⇒Q{\ Displaystyle P \ Rightarrow Q}	п⇐Q{\ Displaystyle P \ Leftarrow Q}	п⇔Q{\ displaystyle P \ Leftrightarrow Q}
		И (союз)	ИЛИ (дизъюнкция)	XOR (исключающее или)	XNOR ( исключая ни)	условное «если-то»	условное «тогда-если»	двусмысленное выражение «если и только если»
куда Т значит правда и F означает ложь

Сжатые таблицы истинности для бинарных операторов

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

Унарные операции