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

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

Что такое таблицы истинности

Определение

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

Таблица истинности необходима для совершения логических операций. Она включает в себя n+1 столбцы и 2ⁿ строки, где n — число используемых переменных. В первых n столбцах представлены разные значения аргументов функции, а в n+1 столбце представлены значения функции, которые она принимает на данном наборе аргументов.

Набором называется совокупность значений переменных. А = 0, В = 1. В случае, когда количество переменных n, число различных наборов будет равно 2^N. Например, для трех переменных число разных наборов будет равно 2³ = 8.

Для создания таблиц истинности используются обозначения логических значений 0 (ложь) и 1 (истина).

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

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

Логические операции

Определение

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

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

К логическим операциям относятся конъюнкция, дизъюнкция, импликация, разделительная дизъюнкция, эквиваленция, антиконъюнкция, антидизъюнкция.

Логические выражения

Определение

Логическое выражение — это запись, принимающая логическое значение «истина» или «ложь».

Их можно разделить на два типа:

• выражения, использующие операции сравнения и принимающие логические значения. Например, выражение a < b, где a = 12, а b = 9, равно значению «ложь»;
• логические выражения, которые связаны с логическими величинами и операциями. Например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина.

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

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

Инверсия

Определение

Инверсия или логическое отрицание — это логическая операция, при выполнении которой из данного высказывания получается новое высказывание. Это высказывание является отрицанием исходного высказывания.

Если данное высказывание обозначается буквой A, то отрицание исходного высказывания обозначается следующим образом \([\overline{A}]\). Кроме этого возможно использование условного обозначения \(\neg A\). Читаться это будет как «не А», «А ложно», «неверно, что А», «отрицание А».

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

Конъюнкция

Определение

Конъюнкция — это логическое умножение. Эта операция, для которой требуются два и более логических величины. Конъюнкция соединяет логические высказывания при помощи связки «и». Связка изображается символом ∧.

Конъюнкция может быть истинной только в том случае, если оба высказывания истинны. Например, A ∧ B, если A = ложь, а B = истина, является ложным.

Дизъюнкция

Определение

Дизъюнкция — логическое сложение. Эта логическая операция соединяет два и более высказываний с помощью связки «или». Эта связка обозначается как ∨.

Логическое высказывание будет истинным, если истинно хотя бы одно из условий. Например, A ∨ B истинно, даже если А = истина, а В = ложь. Высказывание будет ложным только в том случае, если ложны и А, и В.

Правила составления таблицы истинности

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

Строить таблицы истинности необходимо по следующему алгоритму:

1. Вычислить число переменных в выражении (n).
2. Вычислить общее количество логических операций в выражении.
3. Определить последовательность, в которой будут выполняться логические операции.
4. Установить количество столбцов в таблице — количество переменных и количество операций.
5. Внести в шапку таблицы переменные и операции, соблюдая последовательность, определенную в пункте 3.
6. Высчитать количество строк в таблице, используя формулу m = 2ⁿ
7. Занести в таблицу наборы входных переменных. Они представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2ⁿ−1.
8. Заполнить таблицу, совершая логические операции.

Примеры построения таблицы истинности

Задача

Построим таблицу истинности и решим выражение\( F = (A \vee B) \wedge (¬A \vee ¬B)\). Будем пользоваться приведенным выше алгоритмом.

1. Число переменных в выражении n = 2.
2. Общее количество логических операций в выражении — 5.
3. Последовательность выполнения логических операций — 1, 5, 2, 4, 3.
4. Количество столбцов — 7. Логические переменные (А и В) + логические операции \(\vee\), \(\wedge\), \(¬\), \(\vee\) , \(¬\) = 2 +5 = 7.
5. Количество строк — 5, исходя из m =2ⁿ, таким образом 2² = 4, 4+1 (строка заголовков столбцов) = 5.
6. Заполним таблицу.

Решение

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

F = 0 при A = B = 0 и A = B = 1

Задача

Построим еще одну таблицу истинности и решим выражение \(F = X \vee Y \wedge ¬Z\)

1. Число переменных в выражении n = 3.
2. Общее количество логических операций в выражении — 3.
3. Последовательность выполнения логических операций — 3, 2, 1.
4. Количество столбцов — 6. Логические переменные (X, Y, Z) + логические операции\( \vee\), \(\wedge\), ¬ = 3 + 3 = 6.
5. Количество строк — 9, исходя из m =2ⁿ, таким образом 2³ = 8, 8+1 (строка заголовков столбцов) = 9.
6. Заполним таблицу.

Решение

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

F = 0, при X = Y = Z = 0; при X = Y = 0 и Z = 1.

что это, основные виды, порядок их выполнения

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

Виды операций

В программировании выделяют следующие виды функций:

1. Логическое умножение или конъюнкция.
2. Логическое сложение или дизъюнкция.
3. Логическое отрицание или инверсия.
4. Логическое следование или импликация.
5. Логическая равнозначность или эквивалентность.
6. Стрелка Пирса.
7. Штрих Шеффера.

Логическое умножение (конъюнкция)

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

Для обозначения логического умножения используют союз «и», значки\( \wedge\), \(\&.\)

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

A, B — исходные данные;

A и B — значение, приобретаемое в результате реализации конъюнкции.

Из таблицы следуют свойства логического умножения:

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

Логическое сложение (дизъюнкция)

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

Обозначается дизъюнкция союзом «или», символами +,\( \vee\).

Таблица истинности логического сложения:

A, B — входная информация;

A или B — значение, приобретаемое в результате выполнения дизъюнкции.

Для дизъюнкции справедливы следующие утверждения:

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

Логическое отрицание (инверсия)

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

Условное обозначение логического отрицания: с помощью частицы «не», символов ¯, \(\neg.\)

Таблица истинности инверсии:

A — исходные данные;

не A — значение, приобретаемое в результате логического отрицания.

Логическое следование (импликация)

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

Следование записывается с помощью знака \(\rightarrow.\)

Таблица истинности для импликации:

A — входная информация, означающая условие;

B — входная информация, означающая следствие;

A → B — значение, приобретаемое в результате импликации.

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

Логическая равнозначность (эквивалентность)

Эквивалентность — выражение, являющееся истинным лишь в случае равенства двух входных элементов.

При записи равнозначности используют стрелки \(\Leftrightarrow\), \(\leftrightarrow\), \(\Xi\).

Таблица истинности для равнозначности:

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

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

Данная манипуляция является отрицание логического сложения. Свое название рассматриваемая функция получила от своего автора — американского ученого Чарльза Пирса.

Запись стрелки Пирса осуществляется через знак \(\downarrow\).

Таблица истинности для этой операции следующая:

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

Пример

\((A\;\downarrow\;A)\;\downarrow\;(B\;\downarrow\;B)\;=\;A\;\wedge\;B\) — конъюнкция;

\((A\;\downarrow\;B)\;\downarrow\;(A\;\downarrow\;B)\;=\;A\;\vee\;B\) — дизъюнкция;

\(A\;\downarrow\;A\;=\;\neg\;A\;\) — инверсия;

\(((A\;\downarrow\;A)\;\downarrow\;B)\;\downarrow\;((A\;\downarrow\;A)\;\downarrow\;B)\;=\;A\;\rightarrow\;B\) — импликация.

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

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

Символ Шеффера назван по фамилии своего создателя — американского логика Генри Шеффера — и обозначается посредством знака \(\vert.\)

Таблица истинности для данной функции:

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

Пример

\((A\;\vert\;B)\;\vert\;(A\;\vert\;B)\;=\;A\;\wedge\;B\) — конъюнкция;

\((A\;\vert\;A)\;\vert\;(B\;\vert\;B)\;=\;A\;\vee\;B \) — дизъюнкция;

\(A\;\vert\;A\;=\;\neg\;A \) — инверсия.

Порядок выполнения операций

В составном логическом выражении действия выполняются в такой последовательности:

• инверсия;
• конъюнкция;
• дизъюнкция;
• импликация;
• эквивалентность.

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

Алгебра логики — Информатика — подготовка к ЕГЭ

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

Логическое высказывание — это утверждение, которое может быть либо истинным, либо ложным. Примеры высказываний: «Этот автомобиль черного цвета», «3 меньше 5». Противоречивое утверждение не может быть логическим высказыванием, например «Данное утверждение ложно». Логические высказывания обычно обозначаются латинскими буквами. В алгебре логики определены три основных логических операций с высказываниями и законы для выполнения этих операций. Действия с логическими высказываниями записываются в виде логических выражений.

Итак, для любого логического высказывания возможны два значения:

ИСТИНА — в некоторых языках программирования обозначается как True, в формулах и таблицах используется 1

ЛОЖЬ — в некоторых языках программирования обозначается как False, в формулах и таблицах используется 0

Любую логическую функцию можно представить в виде выражения или в виде таблицы истинности. В таблице истинности в столбцах указаны значения аргументов (переменных, операндов) и значение функции. Количество строк в таблице определяется количеством переменных и равно 2^N, где N — количество переменных.

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

1. Логическое отрицание (Инверсия). Обозначается \( ¬A \), not A, НЕ А, в записи на черновике удобно использовать \( \overline{A} \)

Выражение \( \overline{A} \) истинно тогда, когда \( A \) ложно и ложно, когда \( A \) истинно.

Таблица истинности операции логического отрицания:

2. Логическое умножение (Конъюнкция). Обозначается \( A \) ∧ \( B \) ,  \( A \) and \( B \), \( A \) И \( B \), \( A \) & \( B \), в записи на черновике удобно использовать \( A ⋅ B\)

Выражение \( A ⋅ B\) истинно тогда и только тогда, когда оба высказывания \( A \) и \( B \) истинны.

Таблица истинности операции логического умножения:

3. Логическое сложение (Дизъюнкция). Обозначается \( A \) ∨ \( B \) ,  \( A \) or \( B \), \( A \) ИЛИ \( B \), \( A \) | \( B \), в записи на черновике удобно использовать \( A + B\)

Выражение \( A + B\) ложно тогда и только тогда, когда оба высказывания \( A \) и \( B \) ложны.

Таблица истинности операции логического сложения:

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

4. Исключающее ИЛИ. Обозначается \( A \) XOR \( B \) ,  \( A \) ⊕ \( B \)

Выражение  \( A \) ⊕ \( B \) истинно тогда и только тогда, когда высказывания \( A \) и \( B \) не равны.

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

Исключающее ИЛИ можно выразить: \( \overline{A} ⋅ B + A ⋅ \overline{B} \) 

5. Логическое следование (Импликация). Обозначается \( A \) → \( B \) ,  \( A \) ⇒ \( B \)

Выражение  \( A \) → \( B \) ложно тогда и только тогда, когда высказывание \( A \) истинно, а \( B \) ложно.

Таблица истинности операции логического следования:

Логическое следование можно выразить: \( \overline{A} + B \) 

6. Эквивалентность (Равносильность). Обозначается \( A \) → \( B \) ,  \( A \) ~ \( B \),  \( A \) ⇔ \( B \)

Выражение  \( A \) ≡ \( B \) истинно тогда и только тогда, когда высказывания \( A \) и \( B \) совпадают.

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

Эквивалентность можно выразить: \( (\overline{A} + B) ⋅ (A + \overline{B}) \)

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

1. логическое отрицание
2. логическое умножение
3. логическое сложение
4. исключающее ИЛИ
5. логическое следование
6. эквивалентность

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

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

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

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

Рассмотрим несколько примеров:

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

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

Для того, чтобы построить таблицу истинности выражения нужно:

• Определить количество переменных, участвующих в выражении
• Определить количество составляющих выражение логических операций
• Заполнить строки таблицы всеми возможными наборами значений переменных. Наборы значений лучше представлять в виде двоичных чисел. Например, для трех переменных нужно заполнить восемь строк с 000 до 111.
• Вычислить и заполнить промежуточные операции в таблице
• Вычислить и заполнить значение логического выражения

Задача: Построить таблицу истинности для логического выражения \(  \overline{x} ⋅ y  + x ⋅ \overline{y} \)

Решение: 

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

Строится формула следующим образом:

• В таблице истинности выделяются строки, в которых значение функции истинно.
• Для каждой такой строки таблицы записывается конъюнкция всех переменных следующим образом: если значение переменной истинно, то она записывется в прямом виде, а если ложно, то — с инверсией.
• Все, таким образом полученные, конъюнкции объединяются дизъюнкцией

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

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

Задача: Дана полная таблица истинности некоторой функции. Построить формулу функции по этой таблице.

 1. Удаляем строки со значением функции равным 0

2. Составляем конъюнкции для каждой строки

3. Объединяем все конъюнкции дизъюнкцией:

\( F(x,y,z) = \overline{x} ⋅ y ⋅ \overline{z} + x ⋅ \overline{y} ⋅ \overline{z} + x ⋅ \overline{y} ⋅ z + x ⋅ y ⋅ z \)

 Разбор некоторых задач

Задача: Для какого из указанных \( X \) истинно высказывание \( ¬((X > 2) → (X > 3)) \)?

1) 1     2) 2    3) 3    4) 4

Решение: 

Введем обозначения \( (X > 2) — A, (X > 3) — B \), перепишем логическое выражение в удобной нам форме и упростим его, преобразовав импликацию и применив правило де Моргана:

\( \overline{(A → B)} = \overline{\overline{A} + B} = \overline{\overline{A}} ⋅ \overline{B} = A ⋅ \overline{B} \).   Полученное выражение истинно, когда истинны оба множителя, то есть:

\( \begin{cases}A = 1 \\ \overline{B} = 1 \end{cases} \)    или    \( \begin{cases}X > 2 \\ X ≤ 3 \end{cases} \) , заметим, что утверждение \( (X ≤ 3) \) противоположно утверждению \( (X > 3) \)

Системе неравенств удовлетворяет \( X = 3 \). Ответ: вариант 3.

Задача: Символом  \( F \)  обозначено одно из указанных ниже логических выражений от трех аргументов \( X, Y, Z\). Дан фрагмент истинности выражения  \( F \) :

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

1)  \( ¬X ∧ ¬Y ∧ ¬Z \)     2) \( X ∧ Y ∧ Z \)     3) \( X ∨ Y ∨ Z \)     4) \( ¬X ∨ ¬Y ∨ ¬Z \)

Решение:  Для удобства перепишем выражения в удобной форме:

1)  \( \overline{X} ⋅ \overline{Y} ⋅ \overline{Z} \)     2) \( X ⋅ Y ⋅ Z \)     3) \( X + Y + Z \)     4) \( \overline{X} + \overline{Y} + \overline{Z} \)

Если подходить к решению формально, то надо вычислить значение каждого из выражений для каждого приведенного набора данных таблицы и сравнить их со значением \( F \) из таблицы.

Но можно сразу отвергнуть выражение 2, потому что конъюнкция переменных \( X, Y, Z \) при их значениях равным 1 должно быть истинно, а по таблице ложно. Выражение 3 также следует отвергнуть, так как дизъюнкция переменных \( X, Y, Z \) при их значениях равным 0 должно быть ложным, а по таблице истинно.

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

\( \overline{X} ⋅ \overline{Y} ⋅ \overline{Z} \) = \( \overline{1} ⋅ \overline{0} ⋅ \overline{0}  = 0 ⋅ 1 ⋅ 1 = 0\)

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

\( \overline{X} + \overline{Y} + \overline{Z} \) = \( \overline{1} + \overline{0} + \overline{0}  = 0 + 1 + 1 = 1\)

\( \overline{X} + \overline{Y} + \overline{Z} \) = \( \overline{0} + \overline{0} + \overline{0}  = 1 + 1 + 1 = 1\)

\( \overline{X} + \overline{Y} + \overline{Z} \) = \( \overline{1} + \overline{1} + \overline{1}  = 0 + 0 + 0 = 0\)

Ответ: 4.

Задача: Какое из приведенных имен соответствует условию:

(Первая буква согласная) ∨ (Вторая буква гласная) → (В слове 4 буквы)

1) МИХАИЛ     2) ГРИГОРИЙ     3) ЕВГЕНИЙ     4) ИОЛАНТА ?

Решение: Обозначим высказывания: 

(Первая буква согласная) — A
(Вторая буква гласная)  — B
(В слове 4 буквы) — C

Тогда выражение получит вид: \( A + B → C \). 

Преобразуем его: \( A + B → C = \overline{(A + B)} + C  = \overline{A} ⋅ \overline{B} + C \) 

Условие задачи будет выглядеть: \( \overline{A} ⋅ \overline{B} + C = 1\). Но так как во всех приведенных именах больше четырех букв, то  \( C = 0 \)  и условие принимает вид \( \overline{A} ⋅ \overline{B} = 1\), то есть:

\( \begin{cases}\overline{A} = 1 \\ \overline{B} = 1 \end{cases} \)    или    \( \begin{cases} \text{(Первая буква гласная)} \\ \text{(Вторая буква согласная)} \end{cases} \)

Заметим, что оба утверждения противоположны исходным. Этим условиям отвечает только вариант 3.

Задача: Каково наименьшее натуральное число \( X\), при котором истинно высказывание:

\( (X^{2} < 80) → ((X + 1)^{2} > 80)  \) ?

Решение:  Обозначим \( (X^{2} < 80) \) — A, \( ((X + 1)^{2} > 80)  \) — B, тогда получим условие задачи в виде:

\( A → B  \), преобразовываем: \( \overline{A} + B \). Полученное выражение истинно, когда истинно одно из слагаемых. Рассмотрим оба случая:

1. \( X^{2} ≥ 80 \). В задаче речь идет о натуральных числах, поэтому отрицательные значения не рассматриваем: \( X ≥ 4\sqrt{5} \). Ближайшее натуральное число 9, поэтому \( X ≥ 9 \)
2. \( (X + 1)^{2} > 80 \),    \( X + 1 > 4\sqrt{5} \),   \( X > 4\sqrt{5} — 1 \),   \( X ≥ 8\).

 Получается, что высказывание истинно при  \( X ≥ 9 \) или  при \( X ≥ 8 \). Наименьшее число 8.

Задача: Укажите значения переменных \( K, L, M, N \), при которых ложно логическое выражение:

\( (¬K ∨ M) → (¬L ∨ M ∨ N) \)

Ответ запишите в виде строки их четырех символов — значений переменных \( K, L, M, N \) (в указанном порядке). Так, например, строка 1101 соответствует тому, что \( K = 1, L = 1, M = 0, N = 1 \)

Решение: Надо решить уравнение \( (\overline{K} + M) → (\overline{L} + M + N) = 0\). Преобразовываем:

\( \overline{(\overline{K} + M)} + (\overline{L} + M + N) = 0\),  \( (K ⋅ \overline{M}) + (\overline{L} + M + N) = 0\), оба выражения в скобках должны быть ложны, поэтому получаем систему уравнений:

\( \begin{cases}\overline{L} + M + N = 0\\ K ⋅ \overline{M} = 0 \end{cases} \) 

Чтобы дизъюнкция была бы ложной, должны быть ложны все переменные, поэтому из первого уравнения получаем, что \( L = 1, M = 0, N = 0 \). Подставляем \( M = 0\) во второе: \(K ⋅ \overline{0} = 0 \), \(K ⋅ 1 = 0 \), получаем \( K = 0\)

Записываем значения переменных в указанном порядке: 0100

Задачи для самостоятельного решения

• Укажите, какое логическое выражение равносильно выражению (A ∧ ¬B) ∨ (¬A ∧ B) ∧ (A ∨ B)

  1) (A ∨ ¬B) ∧ (¬A ∨ B)

  2) ¬A ∧ ¬B

  3) A ∧ B

  4) A ∧ ¬B ∨ ¬A ∧ B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∨ B) ∧ ¬(A ∧ ¬(B ∧ ¬A))

  1) (A ∨ ¬B) ∧ (¬A ∨ B)

  2) ¬A ∧ ¬B

  3) A ∨ B

  4) (A ∧ B) ∨ ¬A 

• Укажите, какое логическое выражение равносильно выражению (¬A ∧ B) ∨ (A ∧ B ∧ (A ∨ ¬B))

  1) A ∧ B

  2) ¬A

  3)  B

  4) A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(¬A ∨ B) ∧ ¬(A ∧ ¬(B ∨ ¬A))

  1) ¬A ∨ B

  2) 0

  3) 1

  4) B ∨ ¬A

• Укажите, какое логическое выражение равносильно выражению (A ∧ B) ∨ (¬A ∨ B) ∧ (A ∨ ¬B)

  1) (A ∨ B) ∨ (¬A ∨ ¬B)

  2) ¬A ∧ ¬B

  3) A ∧ B

  4) A ∧ B ∨ ¬A ∧ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∨ ¬B) ∧ ¬(¬A ∧ ¬(¬B ∨ A))

  1) ¬A ∨ B

  2) 0

  3) 1

  4) B ∨ ¬A

• Укажите, какое логическое выражение равносильно выражению (A ∨ ¬B) ∧ (¬A ∧ B ∨ A ∧ B)

  1) A ∧ B

  2) ¬A ∧ B

  3) A ∨ ¬B

  4) A ∨ B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∧ B) ∧ ¬(A ∨ ¬(¬B ∨ A ))

  1) A ∧ B

  2) ¬A ∧ ¬B

  3) A ∨ ¬B

  4) ¬A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению (A ∨ B) ∧ ((A  ∧ ¬B) ∨ (¬A  ∧ B ))

  1) ¬A ∧ B

  2) A  ∧ ¬B ∨ ¬A  ∧ B

  3) A ∨ ¬B

  4) (¬A ∨ B)  ∧  (A ∨ ¬B)

• Укажите, какое логическое выражение равносильно выражению ¬(A ∧ ¬B) ∧ ¬(A ∨ ¬(¬B ∧ A ))

  1) A ∧ ¬B

  2) 0

  3) 1

  4) ¬A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∧ B) ∧ ¬(A  ∧ ¬(B ∧ A ))

  1) A ∧ B

  2) ¬B

  3) ¬A

  4) 1

• Укажите, какое логическое выражение равносильно выражению (A ∧ ¬B) ∨ ¬(¬A ∨ ¬(B ∨ A ))

  1) A ∧ ¬B

  2) A

  3) 1

  4) ¬B

• Укажите, какое логическое выражение равносильно выражению (¬A ∨ B) ∧ (¬A ∧ B) ∧ (¬A ∨ ¬B)

  1) ¬A ∧ B

  2) 0

  3) ¬A ∧ B ∨ A ∧ ¬B

  4) ¬A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∧ ¬B) ∧ ¬(A ∧ B) ∧ (A ∨ ¬B)

  1) A ∨ B

  2) 0

  3) 1

  4) ¬A ∧ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(¬A ∨ B) ∨ ¬(A ∨ ¬(¬B ∧ A))

  1) 0

  2) ¬A

  3) ¬B

  4) ¬A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∧ B ∧ ¬C) ∧ (¬A ∨ ¬(B ∧ ¬C))

  1) A ∨ B ∨ C

  2) A ∧ B ∧ C

  3) ¬A ∧ ¬B ∧ C

  4) ¬A ∨ ¬B ∨ C

• Укажите, какое логическое выражение равносильно выражению ¬(¬A ∧ ¬B ∧ C) ∧ (A ∨ ¬(B ∧ ¬C))

  1) A ∨ B

  2) A ∧ B ∧ C

  3) ¬A ∧ ¬B ∧ C

  4) ¬A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению ¬(A ∨ B ∨ ¬C) ∧ (A ∨ ¬(B ∧ C))

  1) 1

  2) A ∧ B ∧ C

  3) 0

  4) ¬A ∨ ¬B

• Укажите, какое логическое выражение равносильно выражению (A ∧ ¬(B ∧ ¬C)) ∧ (A ∨ ¬(¬B ∧ C))

  1) A ∨ B

  2) A ∧ B ∧ C

  3) 0

  4) 1

• Укажите, какое логическое выражение равносильно выражению ¬(A ∨ B ∨ ¬C) ∨ ¬(¬(A ∧ ¬B) ∨ ¬C)

  1) A ∨ ¬B

  2) A ∧ ¬B ∨ C

  3) ¬A  ∧ ¬B ∧ C ∨ A ∨ ¬B ∨ ¬C

  4) ¬B ∧ C

• Укажите, какое логическое выражение равносильно выражению ¬(A ∧ B) ∧ ¬(C ∨ ¬A) ∧ (B ∧ ¬C)

  1) A ∧ ¬B ∨ ¬B ∧ ¬C

  2) 0

  3) ¬A ∧ B ∧ C

  4)  A ∨ ¬B ∨  ¬C

• Укажите какая таблица истинности соответствует логической функции F = (A ∧ B) ∨ (¬B ∧ ¬C)

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  1)		A	B	C	F		2)		A	B	C	F		3)		A	B	C	F		4)		A	B	C	F
  		0	0	0	1				0	0	0	1				0	0	0	0				0	0	0	0
  		0	0	1	0				0	0	1	1				0	0	1	0				0	0	1	1
  		0	1	0	0				0	1	0	0				0	1	0	1				0	1	0	0
  		0	1	1	0				0	1	1	1				0	1	1	1				0	1	1	1
  		1	0	0	1				1	0	0	0				1	0	0	1				1	0	0	1
  		1	0	1	0				1	0	1	1				1	0	1	1				1	0	1	0
  		1	1	0	1				1	1	0	0				1	1	0	0				1	1	0	0
  		1	1	1	1				1	1	1	0				1	1	1	0				1	1	1	1

  Задачу решить составлением таблицы истинности функции.

• Укажите какая таблица истинности соответствует логической функции F = (A ∧ ¬B) ∨ (¬A ∧ C) ∨ (¬B ∧ C)

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  1)		A	B	C	F		2)		A	B	C	F		3)		A	B	C	F		4)		A	B	C	F
  		0	0	0	0				0	0	0	0				0	0	0	0				0	0	0	0
  		0	0	1	0				0	0	1	1				0	0	1	1				0	0	1	1
  		0	1	0	1				0	1	0	0				0	1	0	1				0	1	0	0
  		0	1	1	0				0	1	1	1				0	1	1	0				0	1	1	1
  		1	0	0	1				1	0	0	1				1	0	0	1				1	0	0	1
  		1	0	1	1				1	0	1	1				1	0	1	1				1	0	1	0
  		1	1	0	0				1	1	0	0				1	1	0	0				1	1	0	1
  		1	1	1	0				1	1	1	0				1	1	1	0				1	1	1	0

  Задачу решить составлением таблицы истинности функции.

• Укажите какая таблица истинности соответствует логической функции F = (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C) ∨  (A ∧ ¬B ∧ ¬C)

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  1)		A	B	C	F		2)		A	B	C	F		3)		A	B	C	F		4)		A	B	C	F
  		0	0	0	0				0	0	0	0				0	0	0	0				0	0	0	0
  		0	0	1	0				0	0	1	1				0	0	1	1				0	0	1	1
  		0	1	0	0				0	1	0	0				0	1	0	1				0	1	0	0
  		0	1	1	0				0	1	1	1				0	1	1	0				0	1	1	1
  		1	0	0	1				1	0	0	0				1	0	0	0				1	0	0	1
  		1	0	1	1				1	0	1	1				1	0	1	1				1	0	1	0
  		1	1	0	0				1	1	0	0				1	1	0	0				1	1	0	0
  		1	1	1	1				1	1	1	0				1	1	1	0				1	1	1	0

  Задачу решить составлением таблицы истинности функции.

• Символом  F  обозначено одно из указанных ниже логических выражений от трех аргументов A, B, C. Укажите какое выражение соответствует таблице истинности:

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  A	B	C	F
  0	0	0	1
  0	0	1	0
  0	1	0	1
  0	1	1	0
  1	0	0	0
  1	0	1	1
  1	1	0	0
  1	1	1	1

  1) A ∧ C ∨ ¬B ∧ C

  2) ¬A ∧ ¬C ∨ A ∧ C

  3) ¬B ∧ C ∨ A ∧ B

  4) A ∧ ¬C ∨ B ∧ ¬C

  По приведенной таблице запишите логическую функцию и преобразуйте ее

• Символом  F  обозначено одно из указанных ниже логических выражений от трех аргументов A, B, C. Укажите какое выражение соответствует таблице истинности:

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  A	B	C	F
  0	0	0	0
  0	0	1	1
  0	1	0	0
  0	1	1	1
  1	0	0	1
  1	0	1	0
  1	1	0	1
  1	1	1	0

  1) A ∧ ¬C ∨ ¬A ∧ C

  2) ¬A ∧ ¬C ∨ A ∧ C

  3) ¬B ∧ C ∨ A ∧ B

  4) A ∧ ¬C ∨ B ∧ ¬C

• Символом  F  обозначено одно из указанных ниже логических выражений от трех аргументов A, B, C. Укажите какое выражение соответствует таблице истинности:

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  A	B	C	F
  0	0	0	0
  0	0	1	1
  0	1	0	0
  0	1	1	0
  1	0	0	0
  1	0	1	1
  1	1	0	0
  1	1	1	1

  1) A ∧ ¬C ∨ ¬B ∧ C

  2) ¬A ∧ ¬B ∨ A ∧ C

  3) ¬B ∧ ¬C ∨ A ∧ C

  4) A ∧ ¬C ∨ B ∧ ¬C

  По приведенной таблице запишите логическую функцию и преобразуйте ее

• Символом  F  обозначено одно из указанных ниже логических выражений от трех аргументов A, B, C. Укажите какое выражение соответствует таблице истинности:

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  A	B	C	F
  0	0	0	1
  0	0	1	1
  0	1	0	0
  0	1	1	1
  1	0	0	0
  1	0	1	1
  1	1	0	0
  1	1	1	0

  1) A ∧ ¬C ∨ ¬B ∧ C

  2) ¬A ∧ ¬B ∨ ¬A ∧ C ∨ ¬B ∧ C

  3) A ∧ ¬B ∨ A ∧ C ∨ ¬B ∧ C

  4) A ∧ ¬C ∨ B ∧ ¬C

  По приведенной таблице запишите логическую функцию и преобразуйте ее

• Символом  \( F \)  обозначено одно из указанных ниже логических выражений от трех аргументов \( X, Y, Z \) . Дан фрагмент истинности выражения  \( F \) :

  
  

  
  

  
  

  
  

  \( X \)	\( Y \)	\( Z \)	\( F \)
  0	0	0	1
  0	0	1	1
  1	1	0	0

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

  1)  \( ¬(X ∧ Y) ∨  Z \)     2) \( ¬(X ∨ Y ∨  Z) \)     3) \( X ∧ Y ∧ ¬Z \)     4) \( ¬X ∨ Y ∧ ¬Z \)

• Символом  \( F \)  обозначено одно из указанных ниже логических выражений от трех аргументов \( X, Y, Z \) . Дан фрагмент истинности выражения  \( F \) :

  
  

  
  

  
  

  
  

  \( X \)	\( Y \)	\( Z \)	\( F \)
  1	0	1	1
  1	1	0	0
  1	1	1	0

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

  1)  \( ¬(X ∧ Y) ∨  Z \)     2) \( X ∨ ¬Z → ¬Y \)     3) \( X ∧ Y ∧ ¬Z \)     4) \( ¬Y → X ∨ ¬Z \)

• Символом  \( F \)  обозначено одно из указанных ниже логических выражений от трех аргументов \( X, Y, Z \) . Дан фрагмент истинности выражения  \( F \) :

  
  

  
  

  
  

  
  

  \( X \)	\( Y \)	\( Z \)	\( F \)
  0	0	1	0
  0	1	0	1
  1	1	1	1

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

  1)  \( Y ∨ (X → Z) \)     2) \( Y ∧ (¬X ∨ ¬Z) \)     3) \( ¬Y → (X ∧ Z) \)     4) \( (Y ∨ X) ∧ ¬Z \)

• Логическая функция F задаётся выражением (z ∨ w) ∧ x ∧ (w ∨ ¬y). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z

  
  

  
  

  
  

  
  

  
  

  Перем.1	Перем.2	Перем.3	Перем.4	Функция
  ?	?	?	?	F
  0	0	1	1	1
  1			1	1
  1	1	1	0	1

  В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (без разделителей).

• Логическая функция F задается выражением (х˄¬у) ˅ (¬х˄z). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных х, у, z. В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем —  буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

  
  

  
  

  
  

  
  

  
  

  
  

  Перем.1	Перем.2	Перем.3	Функция
  ?	?	?	F
  0	0	0	0
  0	0	1	0
  1	1	1	0
  1	0	1	0

   

• Логическая функция F задаётся выражением a ∨ b → c ∧ ¬a. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

  
  

  
  

  
  

  
  

  
  

  Перем.1	Перем.2	Перем.3	Функция
  ?	?	?	F
  0	0	1	1
  0		1	1
  0	1		1

  В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы (без разделителей).

• При заполнении таблицы истинности логической функции ¬(z→y) ∨ w ∨ ¬x Андрей успел заполнить лишь фрагмент из семи различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  ???	???	???	???	¬(z→y) ∨ w ∨ ¬x
  0	0	1	0	1
  0	1	0	0	0
  0	1	0	1	0
  0	1	1	0	1
  1	1	0	0	1
  1	1	0	1	0
  1	1	1	0	1

  Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

   

• Логическая функция F задаётся выражением (a ∧ ¬c) ∨ (¬a ∧ b ∧ c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  ???	???	???	F
  0	0	0	0
  0	0	1	0
  0	1	0	0
  0	1	1	1
  1	0	0	1
  1	0	1	1
  1	1	0	0
  1	1	1	0

  В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы (без разделителей).

• Логическая функция F задаётся выражением ((x→y)→z)→¬x  На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий не повторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

  
  

  
  

  
  

  
  

  ?	?	?	F
  1	1		1
  	1	1	1
  1			1

  В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

• Логическая функция F задаётся выражением (¬x ∧ y ∧ z) ∨ (¬x ∧ y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ ¬z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

  
  

  
  

  
  

  
  

  ?	?	?	F
  0	0	0	1
  1	0	0	1
  1	0	1	1

   В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (без разделителей).

• Логическая функция F задаётся выражением (¬x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  ???	???	???	F
  0	0	0	1
  0	0	1	1
  0	1	0	1
  0	1	1	0
  1	0	0	0
  1	0	1	0
  1	1	0	1
  1	1	1	1

  В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (без разделителей).

   

• Укажите, для какого из указанных значений X истинно высказывание ¬(¬(X > 15)→(x>16)).

  1)  15          2) 16          3)  17          4) 18

   

• Укажите, для какого из указанных значений X истинно высказывание (X > 10)→(50 > (x + 1)).

  1)  40          2) 49          3)  50          4) 51

• Каково наибольшее целое число X, при котором ложно высказывание ((X — 10) ⋅ X + 25 > 0)→(X ⋅ X > 30)?

• Для какого символьного набора ложно высказывание:

  (Первая буква — гласная) → ((Вторая буква — согласная) ∧ (Последняя буква — согласная))

  1) Арбалет        2) Пробка        3) Кран        4) Арка

   

• Какое из приведенных имен удовлетворяет логическому условию:

  ((Первая буква согласная) → (Вторая буква согласная)) ∧ (Последняя буква гласная)

  1) Егор        2) Алена        3) Станислав        4) Татьяна

   

• Для какого из названий животных ложно высказывание:

  (Третья буква гласная) → (Заканчивается на гласную букву) ∨ (В слове 6 букв)?

  1) Пума        2) Леопард        3) Кенгуру        4) Страус

   

• Укажите значения переменных K, L, M и N, которые удовлетворяют логическому уравнению:

  ¬(¬(M ∨ K)) ∧ N ∧ (M → L) = 1

  Ответ запишите в виде строки из четырех символов — значений переменных K, L, M, N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K = 1, L = 1, M = 0, N = 1

• Укажите значения переменных K, L, M и N, которые удовлетворяют логическому уравнению:

  (K → M) ∨ (N ∨ ¬L) = 0

  Ответ запишите в виде строки их четырех символов — значений переменных K, L, M, N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K = 1, L = 1, M = 0, N = 1

• Укажите значения переменных K, L и M, которые удовлетворяют логическому уравнению:

  ¬K ∨ К  ∧ ¬L ∧ ¬M ∨ К  ∧ L ∧ ¬M ∨ К  ∧ L ∧ M = 0

  Ответ запишите в виде строки их четырех символов — значений переменных K, L, M (в указанном порядке). Так, например, строка 110 соответствует тому, что K = 1, L = 1, M = 0

• На числовой прямой даны два отрезка: P = [25, 37] и Q = [32, 50]. Отрезок A таков, что формула

  (x ∈ A)  → ((x ∈ P) ∨ (x ∈ Q))

  тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Какова наибольшая возможная длина отрезка A?

• На числовой прямой даны два отрезка: P = [25, 37] и Q = [32, 50]. Отрезок A таков, что формула

  ((x ∈ A) & ¬(x ∈ Q))  → ((x ∈ P)) & (x ∈ Q))

  тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Какова наибольшая возможная длина отрезка A?

• Даны три отрезка на числовой прямой: A = [5, 12], B = [13, 19], C = [4,Y]. Какому минимальному целому числу может быть равен Y, чтобы выражение выполнялось для любого x? (x ∉ C) → ((X ∈ B) →(x ∈ A)) = 1

  Обозначим: (x ∈ A) как A, (x ∈ B) как B, (x ∈ C) как C и преобразуем выражение: \( \overline{C} → (B → A) = \overline{C} → (\overline{B} + A) \) \( = C + \overline{B} + A  \)

• На числовой прямой даны два отрезка: P = [5, 13] и Q = [12, 19]. Укажите наибольшую возможную длину промежутка A, для которого формула

  ((x ∈ P) ≡ (x ∈ Q)) → ¬(x ∈ A)

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

• Для какого наименьшего целого числа А формула

  ((x < 5) → (x⋅x ≤ A)) ∧ ((y⋅y ≤ A) → (y ≤ 7))

  тождественно истинна (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

• Для какого наибольшего целого числа А формула

  ((y⋅y ≤ A) → (y ≤ 15)) ∧ ((x ≤ 3) → x⋅x < A))

  тождественно истинна (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

• Сколько существует целых значений А, при которых формула

  ((x ≥ 12) ∧ (x⋅x + 6⋅x < A)) ∨ ((y⋅y + 4⋅y ≥ A) ∧ (y ≤ 4))

  тождественно ложна (то есть принимает значение 0 при любых целых неотрицательных значениях переменных x и y)?

• Известно, что для некоторого отрезка А формула

  ((x ∈ A) → (x² ≤ 81)) ∧ ((x² ≤ 64) → (x ∈ A))

  тождественно истинна (то есть принимает значение 1 при всех вещественных значениях переменной x). Какую наибольшую длину может иметь отрезок A?

• Укажите наименьшее целое значение А, при котором выражение

  (y + 2x < A) ∨ (x > 20) ∨ (y > 20)

  истинно для любых целых положительных значений x и y. 

• Укажите наименьшее целое значение А, при котором выражение

  (y — 2x < A) ∨ (x > 20) ∨ (y > 20)

  истинно для любых целых положительных значений x и y. 

• Укажите наибольшее целое значение А, при котором выражение

  (y — 2x > A) ∨ (x > 20) ∨ (y > 20)

  истинно для любых целых положительных значений x и y. 

• Укажите наименьшее целое значение А, при котором выражение

  (y + 2x < A) ∨ (x > 20) ∨ (y > x)

  истинно для любых целых положительных значений x и y. 

• Укажите наименьшее целое значение А, при котором выражение

  (y⋅x < A) ∨ (x ≥ 9) ∨ (y > x)

  истинно для любых целых положительных значений x и y. 

• Укажите наименьшее целое значение A, при котором выражение

  (3x + 2y ≠ 30) ∨ (A > x) ∧ (A > y)

  истинно для любых целых неотрицательных значений x и y.

• Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

  Для какого наибольшего натурального числа А формула

  ¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))

  тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

информатика и логика — Лекция 3. Логические операции и таблицы истинности.

Операция «НЕ».

   Если высказывание А – истинно, то высказывание «НЕ А» — ложно и наоборот.

   Логическое отрицание (inversion – лат. переворачиваю) – присоединение частицы «не» к сказуемому простого высказывания A.

Пример:

   A: «Моя собака любит кашу».

¬A: «Моя собака НЕ любит кашу».

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

Пример:

   A: «Вася умеет кататься на коньках».

¬A: «НЕВЕРНО, ЧТО Вася умеет кататься на коньках».

   Свойства инверсии:

1. ¬¬(A)=A.

Операция «И».

   Конъюнкция истина тогда и только тогда, когда высказывания «A» и «B» истины.

   Логическое умножение (conjunction – лат. связываю) – соединение двух простых высказываний A и B в одно составное с помощью союза «и».

Пример: 

      A: «Киев является столицей Украины».

      B: «В Киеве проживают  тыс. человек».

A∩B: «Киев – столица Украины И в нем проживают  тыс. человек».

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

Пример:

      A: «Киев — столица Украины».

      B: «Москва – столица России».

A∩B: «Киев – столица Украины, А Москва – столица России» или «Киев – столица Украины, НО Москва – столица России».

   Свойства конъюнкции:

Операция «ИЛИ».

   Дизъюнкция ложна тога и только тогда, когда оба высказывания «A» и «B», ложны.

   Логическое сложение (disjunction – лат. различаю) – соединение двух простых высказываний A и B с помощью союза «или», в неисключающем смысле, то есть, одно высказывание не исключает другое.

Пример:

      A: «Число 10 кратно 5».

      B: «28 меньше 30».

A∪B: «Число 10 кратно 5 ИЛИ 28 меньше 30».

Свойства дизъюнкции:

Операция «Исключающее ИЛИ».

   Строгая дизъюнкция истинна тогда и только тогда, когда высказывания «A» и «B» не равны меду собой.

   Строгая дизъюнкция соответствует оборотам речи «или…, или…», «либо…, либо…».

Пример:

      A: «На улице зима».

      B: «На улице весна»

A⊕B: «ИЛИ на улице зима, ИЛИ на улице весна» или «ЛИБО на улице зима, ЛИБО на улице весна».

Свойства строгой дизъюнкции:

Операция «Если – то».

   Импликация ложна тогда и только тогда, когда посылка «A» истина, а заключение «B» –ложно.

   Импликация (implication – лат. тесно связываю) — соединение двух простых высказываний A и B с помощью конструкции «Если…, то…».

Пример:

       A: «Завтра будет -200».

       B: «Я пойду в школу».

A→B: «ЕСЛИ завтра будет -200, ТО я пойду в школу».

   В русском языке для обозначения импликации кроме конструкции «если…, то..» можно использовать конструкции «Из… следует…», «… имплицирует …», «… достаточно для …» и «… необходимо для…».

Пример:

       A: «Мне дадут зарплату».

       B: «Я куплю мопед».

A→B: «ИЗ того, что мне дадут зарплату, СЛЕДУЕТ, что я куплю мопед», «Мне дадут зарплату ИМПЛИЦИРУЕТ тому, что я куплю мопед», «Мне дадут зарплату и этого ДОСТАТОЧНО ДЛЯ покупки мопеда» или «Получение зарплаты НЕОБХОДИМО ДЛЯ покупки мопеда».

Свойства импликации:

Равносильность.

   Эквиваленция истина тогда и только тогда, когда выражения «A» и «B» равны.

   Эквивалентность (aequivalens – фр. равноценное) – соответствует оборотам речи «тогда и только тогда» и «в том и только в том случае».

Пример: 

        A: «Пете поставят хорошую оценку».

        B: «Петя выучит уроки».

A↔B: «Пете поставят хорошую оценку тогда и только тогда, когда Петя выучит уроки».

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

Пример:

        A: «Четырехугольник – это прямоугольник».

        B: «У четырехугольника два угла по 900».

A↔B: «Для того, чтобы четырехугольник был прямоугольником, НЕОБХОДИМО И ДОСТАТОЧНО, чтобы два его угла были прямыми».

Свойства эквивалентности:

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

   Стрелка Пирса принимает истинное значение тогда и только тогда, когда оба выражения «A» и «B» ложны.

   Стрелка Пирса – логическая операция с двумя переменными, соответствует обороту речи «ни…, ни…».

Пример:

A↓B: «НИ рыба, НИ мясо».

Свойства символа Лукашевича:

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

   Штрих Шеффера принимает ложное значение тогда и только тогда, когда оба выражения «A» и «B» истины.

   Штрих Шеффера – логическая операция с двумя переменными, соответствующая обороту речи «не… или не…».

Пример:

A∣A= «На улице НЕ теплая погода ИЛИ мы НЕ идем купаться».

Свойства штриха Шеффера:

   Основные положения:

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

   Равносильные функции — это функции у которых совпадают таблицы истинности. 

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

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

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

• Инверсия;
• Конъюнкция;
• Дизъюнкция;
• Строгая дизъюнкция;
• Импликация;
• Эквиваленция;
• Стрелка Пирса;
• Штрих Шеффера.

    Контрольные вопросы и задания:

1. Что такое таблица истинности и для чего она нужна?

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

3. Докажите свойства строгой дизъюнкции?

4. .5. 6. 

Литература:

1. Ивлев Ю.В. Логика
2. Бочаров В.А., Маркин В.И. Основы логики.
3. Гончаров С.С., Ершов Ю.Л., Самохвалов К.Ф. Введение в логику и методологию науки.
4. Непейвода Н.Н. Прикладная логика.

Построение СКНФ и СДНФ по таблице истинности

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

Нормальная форма существует в двух видах:

1. конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $\left(A\vee \overline{B}\vee C\right)\wedge \left(A\vee C\right)$;

2. дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $\left(A\wedge \overline{B}\wedge C\right)\vee \left(B\wedge C\right)$.

СКНФ

Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:

• не содержит одинаковых элементарных дизъюнкций;

• ни одна из дизъюнкций не содержит одинаковых переменных;

• каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

Правила построения СКНФ по таблице истинности

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

Готовые работы на аналогичную тему

СДНФ

Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:

• не содержит одинаковых элементарных конъюнкций;

• ни одна из конъюнкций не содержит одинаковых переменных;

• каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.

Правила построения СДНФ по таблице истинности

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

Примеры нахождения СКНФ и СДНФ

Пример 1

Записать логическую функцию по ее таблице истинности:

Рисунок 1.

Решение:

Воспользуемся правилом построения СДНФ:

Рисунок 2.

Получим СДНФ:

\[F\left(x_1,\ x_2,\ x_3\right)=\left(\overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\right)\vee \left(\overline{x_1}\wedge \overline{x_2}\wedge x_3\right)\vee \left(x_1\wedge \overline{x_2}\wedge \overline{x_3}\right)\vee \left(x_1\wedge \overline{x_2}\wedge x_3\right)\vee \left(x_1\wedge x_2\wedge x_3\right)\]

Воспользуемся правилом построения СКНФ:

Рисунок 3.

Получим СКНФ:

\[F\left(x_1,\ x_2,\ x_3\right)=\left(x_1\vee \overline{x_2}\vee x_3\right)\wedge \left(x_1\vee \overline{x_2}\vee \overline{x_3}\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee x_3\right)\]

Пример 2

Функция задана таблицей истинности:

Рисунок 4.

Представить эту функцию в виде СДНФ и СКНФ.

Решение:

1. Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.

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

   

   Рисунок 5.

   Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:

   \[F\left(x_1,x_2,x_3,x_4\right)=\left(\overline{x}\wedge \overline{y}\wedge z\wedge f\right)\vee \left(\overline{x_1}\wedge x_2\wedge \overline{x_3}\wedge \overline{x_4}\right)\vee \left(\overline{x_1}\wedge x_2\wedge x_3\wedge x_4\right)\vee \left(x_1\wedge \overline{x_2}\wedge \overline{x_3}\wedge \overline{x_4}\right).\]

2. Запишем логическую функцию в СКНФ.

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

   

   Рисунок 6.

   Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:

   \[F\left(x_1,x_2,x_3,x_4\right)=\left(x_1\vee x_2\vee x_3\vee x_4\right)\wedge \left(x_1\vee x_2\vee x_3\vee \overline{x_4}\right)\wedge \left(x_1\vee x_2\vee \overline{x_3}\vee x_4\right)\wedge \left(x_1\vee \overline{x_2}\vee x_3\vee \overline{x_4}\right)\wedge \left(x_1\vee \overline{x_2}\vee \overline{x_3}\vee x_4\right)\wedge \left(\overline{x_1}\vee x_2\vee x_3\vee \overline{x_4}\right)\wedge \left(\overline{x_1}\vee x_2\vee \overline{x_3}\vee x_4\right)\wedge \left(\overline{x_1}\vee x_2\vee \overline{x_3}\vee \overline{x_4}\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee x_3\vee x_4\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee x_3\vee \overline{x_4}\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee \overline{x_3}\vee x_4\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee \overline{x_3}\vee \overline{x_4}\right).\]

Свойства логических операций — урок. Информатика, 8 класс.

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

Переместительный (коммутативный) закон:

• для логического умножения: 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.

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

A¯¯=A.

Обрати внимание!

Двойное отрицание исключает отрицание.

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

• для логического умножения: A&A¯=0;
• для логического сложения: A∨A¯=1.

Обрати внимание!

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

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

• для логического умножения: A&A=A;
• для логического сложения: A∨A=A.

Законы операций с \(0\) и \(1\):

• для логического умножения: A&0=0; A&1=A;
• для логического сложения: A∨0=A; A∨1=1.

Законы общей инверсии:

• для логического умножения: A&B¯=A¯∨B¯;
• для логического сложения: A∨B¯=A¯&B¯.

Законы алгебры логики могут быть доказаны с помощью таблиц истинности. Докажем распределительный закон для логического сложения:
A∨B&C=A∨B&A∨C.

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

Источники:

Босова Л. Л., Босова А. Ю., Информатика: учебник для 8 класса. М. : БИНОМ. Лаборатория знаний, 30 с.

Что такое таблица истинности (диаграмма)? Определение Webopedia

Главная »СРОК» Т »

Форрест Страуд

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

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

Как создать таблицу истинности

Первый шаг в создании таблицы истинности — определить количество переменных и строк, необходимых для таблицы, а затем записать все возможные комбинации (обычно обозначенные как « p » и « q »).

Для создания базовой таблицы истинности «И» (соединения) мы будем использовать следующий пример:

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

В этом примере « p » представляет собой первую предпосылку, при которой вы поступаете в государственный университет, а « q » означает получение работы с шестизначной суммой после окончания университета.

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

Пять основных операций в таблицах истинности

Таблицы истинности используют пять основных операций:

1. Соединение: Операция «И», в которой оба аргумента должны быть true , чтобы сам оператор был true

2. Дизъюнкция: Операция «или», в которой оба аргумента должны быть false , чтобы сам оператор был false

3. Отрицание: Операция «не» — это операция, противоположная (или дополняющая) исходному значению

.

4.Условный: Операция «если — то», при которой утверждение неверно только тогда, когда первая посылка верна, а вторая ложна

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

НОВОСТИ ВЕБОПЕДИИ

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

ВВЕДЕНИЕ ЛОГИЧЕСКАЯ ТАБЛИЦА ОПЕРАЦИЙ И ПРАВИЛА.

Презентация на тему: «ВВЕДЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ ИСТИНА ТАБЛИЦА И ПРАВИЛА.» — стенограмма презентации:

1

ВВЕДЕНИЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ ИСТИННАЯ ТАБЛИЦА И ПРАВИЛА

2

ВВЕДЕНИЕ 1854: Джордж Буль опубликовал логическую алгебру, известную сегодня как Булева алгебра. Это удобный и систематический способ выражения и анализа работы логических схем.1938: Клод Шеннон первым применил работу Буля к анализу и проектированию логических схем.

3

ТАБЛИЦА ИСТИНЫ ТАБЛИЦА ИСТИНЫ — это таблица, которая представляет все возможные значения логических переменных вместе со всеми возможными результатами данной комбинации значений.

4

5

6

ЛОГИЧЕСКИЕ ОПЕРАТОРЫ / оператор GATE NOT / оператор GATE OR / оператор GATE AND / GATE

7

NOT OPERATOR / GATE Этот оператор работает с одной переменной.Операция, выполняемая оператором НЕ, называется дополнением. Символ оператора НЕ представлен знаком ~. Таким образом, X означает дополнение к X.

8

ТАБЛИЦА ИСТИНЫ ДЛЯ НЕ ОПЕРАТОРА / ВОРОТА Допустим только одно из двух значений 0 и 1. Где 0 означает ложное значение, а 1 означает истинное значение

11

OR OPERATOR / GATE Этот оператор обозначает операцию, называемую логическим сложением.Этот символ представлен знаком +. Таким образом, X + Y можно читать как X OR Y. Для операции OR возможные комбинации входов и выходов следующие.

определение таблицы истинности и синонимов таблицы истинности (английский)

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

На практике таблица истинности состоит из одного столбца для каждой входной переменной (например, A и B) и одного последнего столбца для всех возможных результатов логической операции, которую эта таблица должна представлять (например, A XOR B). Поэтому каждая строка таблицы истинности содержит одну возможную конфигурацию входных переменных (например, A = истина, B = ложь) и результат операции для этих значений.См. Примеры ниже для дальнейшего пояснения. Людвигу Витгенштейну часто приписывают их изобретение в «Логико-философском трактате». ^[1]

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

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

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

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

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

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

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

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

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

Вот таблица истинности, дающая определения всех 16 возможных функций истинности двух двоичных переменных (P, Q, таким образом, являются логическими переменными):

, где T = истина и F = ложь.

Ключ:

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

Логическая связь

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

Таблица истинности для p AND q (также записывается как p ∧ q , Kpq , p & q или p q ) выглядит следующим образом:

В терминах обычного языка, если и p , и q истинны, то соединение p ∧ q истинно.Для всех других присвоений логических значений p и q соединение p ∧ q является ложным.

Также можно сказать, что если p , то p ∧ q равно p , иначе p ∧ q равно p .

Логическая дизъюнкция

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

Таблица истинности для p OR q (также записывается как p ∨ q , Apq , p || q или p + q ) выглядит следующим образом:

Указано на английском языке, если p , то p ∨ q равно p , иначе p ∨ q равно q .

Логическое следствие

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

Таблица истинности, связанная с материальным условным условием , если p, то q (обозначено как p → q ), а логическое следствие p подразумевает q (обозначено как p ⇒ q или Cpq ) выглядит следующим образом :

Также может быть полезно отметить, что p → q эквивалентно ¬p ∨ q .

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

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

Таблица истинности для p XNOR q (также записывается как p ↔ q , Epq , p = q или p ≡ q ) выглядит следующим образом:

Итак, p EQ q истинно, если p и q имеют одинаковое значение истинности (оба истинны или оба ложны), и ложь, если они имеют разные значения истинности.

Эксклюзивная дизъюнкция

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

Таблица истинности для p XOR q (также записывается как p ⊕ q , Jpq или p ≠ q ) выглядит следующим образом:

Для двух предложений XOR также может быть записано как (p = 1 ∧ q = 0) ∨ (p = 0 ∧ q = 1).

Логическая И-НЕ

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

Таблица истинности для p NAND q (также записывается как p ↑ q , Dpq или p | q ) выглядит следующим образом:

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

В случае логического И-НЕ оно явно выражается как соединение НЕ и И.

Отрицание конъюнкции: ¬ ( p ∧ q ) и дизъюнкция отрицаний: (¬ p ) ∨ (¬ q ) могут быть представлены в виде таблицы:

Логический NOR

Логическое ИЛИ — это операция над двумя логическими значениями, обычно значениями двух предложений, которая дает значение истинно , если оба его операнда ложны.Другими словами, он выдает значение false , если хотя бы один из его операндов истинен. ↓ также известен как стрелка Пирса в честь ее изобретателя Чарльза Сандерса Пирса и является единственным достаточным оператором.

Таблица истинности для p NOR q (также записывается как p ↓ q , Xpq или p ⊥ q ) выглядит следующим образом:

Отрицание дизъюнкции ¬ ( p ∨ q ) и соединение отрицаний (¬ p ) ∧ (¬ q ) можно табулировать следующим образом:

Проверка табличных производных для NAND и NOR при каждом присвоении логических значений функциональным аргументам p и q , производит идентичные шаблоны функциональных значений для ¬ ( p ∧ q ), как для (¬ p ) ∨ (¬ q ), а для ¬ ( p ∨ q ) как для (¬ p ) ∧ (¬ q ).Таким образом, первое и второе выражения в каждой паре логически эквивалентны и могут заменять друг друга во всех контекстах, которые относятся исключительно к их логическим значениям.

Эта эквивалентность — один из законов Де Моргана.

Приложения

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

Это демонстрирует тот факт, что p → q логически эквивалентно ¬ p ∨ q .

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

Вот таблица истинности, дающая определения наиболее часто используемых 6 из 16 возможных функций истинности двух двоичных переменных (P, Q, таким образом, являются логическими переменными):

Ключ:

T = правда, F = ложь

= И (логическое соединение)

= ИЛИ (логическая дизъюнкция)

= XOR (исключающее ИЛИ)

= XNOR (исключая ни)

= условное «если-то»

= условное «(то) -если»

двусмысленное выражение или «если и только если» логически эквивалентно: XNOR (исключающее или).

Логические операторы также можно визуализировать с помощью диаграмм Венна.

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

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

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

Таблицы истинности в цифровой логике

Таблицы истинности также используются для определения функциональности аппаратных справочных таблиц (LUT) в цифровых логических схемах. n значений (или строк в табличном формате выше), полностью определяющих логическую функцию для LUT. Представляя каждое логическое значение как бит в двоичном числе, значения таблицы истинности могут быть эффективно закодированы как целочисленные значения в программном обеспечении автоматизации электронного проектирования (EDA). Например, 32-битное целое число может кодировать таблицу истинности для LUT с максимум 5 входами.

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

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

Применение таблиц истинности в цифровой электронике

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

A B | C R
1 1 | 1 0
1 0 | 0 1
0 1 | 0 1
0 0 | 0 0

где

A = первый операнд
B = второй операнд
C = нести
R = Результат
 

Эта таблица истинности читается слева направо:

• Пара значений (A, B) равна паре значений (C, R).
• Или, в этом примере, A плюс B равно результат R, с Carry C.

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

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

Например, в операции сложения нужно два операнда, A и B. Каждый может иметь одно из двух значений, ноль или один. Количество комбинаций этих двух значений равно 2×2 или четырем. Таким образом, результат — четыре возможных выхода C и R. Если использовать базу 3, размер увеличится до 3×3, или девяти возможных выходов.

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

A B C * | C R
0 0 0 | 0 0
0 1 0 | 0 1
1 0 0 | 0 1
1 1 0 | 1 0
0 0 1 | 0 1
0 1 1 | 1 0
1 0 1 | 1 0
1 1 1 | 1 1

То же, что и предыдущий, но ..
C * = Перенести из предыдущего сумматора
 

См. Также

Список литературы

Дополнительная литература

• Bocheński, Józef Maria (1959), A Précis of Mathematical Logic , перевод французского и немецкого изданий Отто Берда, Д.Рейдель, Дордрехт, Южная Голландия.
• Эндертон, Х. (2001). Математическое введение в логику , второе издание, Harcourt Academic Press. ISBN 0-12-238452-0
• Quine, W.V. (1982), Методы логики , 4-е издание, издательство Гарвардского университета, Кембридж, Массачусетс.

Внешние ссылки

2.1: Операторы и логические операторы

ПРЕДВАРИТЕЛЬНЫЙ ПРОСМОТР \ (\ PageIndex {1} \): составные утверждения

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

• Конъюнкция операторов \ (P \) и \ (Q \) — это утверждение «\ (P \) и \ (Q \)», которое обозначается как \ (P \ wedge Q \). Утверждение \ (P \ wedge Q \) верно только тогда, когда оба \ (P \) и \ (Q \) верны.
• Дизъюнкция операторов \ (P \) и \ (Q \) — это утверждение «\ (P \) или \ (Q \)», и оно обозначается как \ (P \ vee Q \). Утверждение \ (P \ vee Q \) истинно только тогда, когда истинно хотя бы одно из \ (P \) или \ (Q \).
• Отрицание ( утверждения ) утверждения \ (P \) является утверждением «, а не \ (P \)» и обозначается \ (\ urcorner P \).Отрицание \ (P \) истинно, только когда \ (P \) ложно, а \ (\ urcorner P \) ложно, только когда \ (P \) истинно.
• Импликация или условное — это утверждение « Если \ (P \) , то \ (Q \)», которое обозначается как \ (P \ to Q \). Утверждение \ (P \ to Q \) часто читается как «\ (P \) влечет \ (Q \), и мы видели в разделе 1.1, что \ (P \ to Q \) ложно только тогда, когда \ (P \) истинно, а \ (Q \) ложно.

Несколько замечаний по поводу дизъюнкции.
Важно понимать использование оператора «или». В математике мы используем « включительно или », если не указано иное. Это означает, что \ (P \ vee Q \) истинно, когда оба \ (P \) и \ (Q \) истинны, а также когда истинно только одно из них. То есть \ (P \ vee Q \) истинно, если хотя бы одно из \ (P \) или \ (Q \) истинно, или \ (P \ vee Q \) ложно, только когда оба \ (P \ ) и \ (Q \) ложны.

Другое использование слова «или» — это « исключающее или ». Для исключающего или результирующий оператор ложен, если оба утверждения верны.То есть, «\ (P \) эксклюзивное или \ (Q \)» истинно только тогда, когда истинно ровно одно из \ (P \) или \ (Q \). В повседневной жизни мы часто используем эксклюзивное или. Когда кто-то говорит: «На перекрестке поверните налево или идите прямо», этот человек использует исключительное или.

Некоторые комментарии по поводу отрицания . Хотя выражение \ (\ urcorner P \) можно прочитать как «Это не тот случай, когда \ (P \)», часто есть лучшие способы сказать или написать это на английском языке. Например, мы обычно говорим (или пишем):

• Отрицание утверждения «391 простое» означает «391 не простое число».”
• Отрицание утверждения «\ (12 <9 \)» равно «\ (12 \ ge 9 \)».

1. Для выписок

   \ (P \): 15 — нечетное \ (Q \): 15 — простое
   запишите каждое из следующих утверждений как английские предложения и определите

   , истинны они или ложны.
   (а) \ (P \ клин Q \). (б) \ (P \ vee Q \). (c) \ (P \ клин \ urcorner Q \). (г) \ (\ urcorner P \ vee \ urcorner Q \).

2. Для выписок

   P: 15 нечетное R: 15 <17

   запишите каждое из следующих утверждений в символической форме, используя операторы \ (\ wedge \), \ (\ vee \) и \ (\ urcorner \)

   (а) 15 \ (\ ge \) 17.(б) 15 нечетно или 15 \ (\ ge \) 17.
   (в) 15 четно или 15 <17. (d) 15 нечетно и 15 \ (\ ge \) 17.

ПРЕДВАРИТЕЛЬНЫЙ ПРОСМОТР \ (\ PageIndex {2} \): истинные значения утверждений

Мы будем использовать следующие два оператора для всего этого предварительного просмотра:

• \ (P \) — это высказывание «Идет дождь».
• \ (Q \) — это утверждение «Дейзи играет в гольф».

В каждой из следующих четырех частей утверждениям \ (P \) и \ (Q \) будет присвоено значение истинности.Например, в вопросе (1) мы предполагаем, что каждое утверждение истинно. В вопросе (2) мы будем предполагать, что \ (P \) истинно, а \ (Q \) ложно. В каждой части определите значение истинности каждого из следующих утверждений:

(a) (\ (P \ wedge Q \)) Идет дождь, и Дейзи играет в гольф.

(b) (\ (P \ vee Q \)) Идет дождь или Дейзи играет в гольф.

(c) (\ (P \ to Q \)) Если идет дождь, значит, Дейзи играет в гольф.

(d) (\ (\ urcorner P \)) Дождя нет.

Какие из четырех утверждений [от (a) до (d)] верны, а какие — ложны в каждой из следующих четырех ситуаций?

1. Когда \ (P \) истинно (идет дождь) и \ (Q \) истинно (Дейзи играет в гольф).
2. Когда \ (P \) истинно (идет дождь) и \ (Q \) ложно (Дейзи не играет в гольф).
3. Когда \ (P \) ложно (дождь не идет) и \ (Q \) истинно (Дейзи играет в гольф).
4. Когда \ (P \) ложно (дождь не идет) и \ (Q \) ложно (Дейзи не играет в гольф).

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

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

Другие формы условных утверждений

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

Если «соблюдаются определенные условия», то «что-то происходит.”

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

Нам также необходимо знать, что в английском языке существуют другие способы выражения условного оператора \ (P \ to Q \), кроме «Если \ (P \), то \ (Q \)». Ниже приведены некоторые распространенные способы выражения условного оператора \ (P \ to Q \) на английском языке:

Progress Check 2.1: Заявление «Только если»

Напомним, что четырехугольник — это четырехугольник.Пусть \ (S \) представляет следующее истинное условное утверждение:

Если четырехугольник квадрат, то это прямоугольник.

Запишите это условное выражение на английском языке, используя

.

1. слово «всякий раз, когда»
2. фраза «только если»
3. фраза «необходимо»
4. фраза «достаточно для»

Ответ

Добавьте сюда тексты. Не удаляйте сначала этот текст.

Создание таблиц истины

Таблицы истинности для составных утверждений могут быть построены с использованием таблиц истинности для основных связок. Чтобы проиллюстрировать это, мы построим таблицу истинности для. \ ((P \ клин \ urcorner Q) \ к R \). Первым делом нужно определить количество необходимых строк.

• Для таблицы истинности с двумя разными простыми утверждениями необходимы четыре строки, поскольку существует четыре различных комбинации значений истинности для двух утверждений.Мы должны согласовываться с тем, как мы расставляем ряды. В этом тексте мы сделаем это так, чтобы пометить строки для первого оператора (T, T, F, F) и строки для второго оператора (T, F, T, F). Все таблицы истинности в тексте имеют эту схему.
• Для таблицы истинности с тремя разными простыми утверждениями необходимо восемь строк, так как существует восемь различных комбинаций значений истинности для трех утверждений. Наша стандартная схема для этого типа таблицы истинности показана в Таблице 2.2 .

Следующим шагом является определение столбцов, которые будут использоваться. Один из способов сделать это — вернуться назад от формы данного оператора. Для \ ((P \ wedge \ urcorner Q) \ to R \) последний шаг — иметь дело с условным оператором \ ((\ to) \). Для этого нам нужно знать значения истинности \ ((P \ wedge \ urcorner Q) \) и \ (R \). Чтобы определить значения истинности для \ ((P \ wedge \ urcorner Q) \), нам нужно применить правила для оператора конъюнкции \ ((\ wedge) \), и нам нужно знать значения истинности для \ (P \ ) и \ (\ urcorner Q \).

Таблица 2.2 — это полная таблица истинности для \ ((P \ wedge \ urcorner Q) \ to R \) с номерами шагов, указанными внизу каждого столбца. Номера шагов соответствуют порядку заполнения столбцов.

• При заполнении столбца для \ (P \ wedge \ urcorner Q \) помните, что конъюнкция истинна только тогда, когда оба \ (P \) и \ (\ urcorner Q \) истинны.
• При заполнении столбца для \ ((P \ wedge \ urcorner Q) \ to R \) помните, что условное утверждение ложно только тогда, когда гипотеза \ ((P \ wedge \ urcorner Q) \) верна и заключение \ (R \) неверно.

Последний введенный столбец — это таблица истинности для утверждения \ ((P \ wedge \ urcorner Q) \ to R \), использующего настройку в первых трех столбцах.

Проверка выполнения 2.2: Построение таблиц истинности

Создайте таблицу истинности для каждого из следующих утверждений:

1. \ (P \ клин \ urcorner Q \)
2. \ (\ urcorner (P \ клин Q) \)
3. \ (\ urcorner P \ клин \ urcorner Q \)
4. \ (\ urcorner P \ vee \ urcorner Q \)

Есть ли у любого из этих утверждений одна и та же таблица истинности?

Ответ

Добавьте сюда тексты.Не удаляйте сначала этот текст.

Заявление с двумя условными условиями

Некоторые математические результаты сформулированы в форме «\ (P \) тогда и только тогда, когда \ (Q \)» или «\ (P \) необходимо и достаточно для \ (Q \)». Примером может быть: «Треугольник является равносторонним тогда и только тогда, когда его три внутренних угла совпадают». Символическая форма для биконусного утверждения «\ (P \) тогда и только тогда, когда \ (Q \)» есть \ (P \ leftrightarrow Q \). Чтобы определить таблицу истинности для двусмысленного утверждения, поучительно внимательно посмотреть на форму фразы «\ (P \) тогда и только тогда, когда \ (Q \)».Слово «и» предполагает, что это утверждение является союзом. На самом деле это сочетание утверждений «\ (P \), если \ (Q \)» и «\ (P \), только если \ (Q \)». Символическая форма этого соединения: \ ([(Q \ to P) \ wedge (P \ to Q] \).

Progress Check 2.3: Таблица истинности для двухусловного утверждения

Заполните таблицу истинности для \ ([(Q \ to P) \ wedge (P \ to Q] \). Используйте следующие столбцы: \ (P \), \ (Q \), \ (Q \ to P \ ), \ (P \ to Q \) и \ ([(Q \ to P) \ wedge (P \ to Q] \). Последний столбец этой таблицы будет истинным для \ (P \ leftrightarrow Q \ ).

Ответ

Добавьте сюда тексты. Не удаляйте сначала этот текст.

Другие формы двусмысленного утверждения

Как и в случае с условным оператором, существует несколько распространенных способов выражения двузонального оператора \ (P \ leftrightarrow Q \) на английском языке.

Пример

• \ (P \) есть и только если \ (Q \).
• \ (P \) необходимо и достаточно для \ (Q \).
• \ (P \) влечет \ (Q \), а \ (Q \) влечет \ (P \).

Тавтологии и противоречия

Определение: тавтология

Тавтология — это составное утверждение S, которое истинно для всех возможных комбинаций значений истинности составных утверждений, которые являются частью \ (S \). Противоречие — это составное утверждение, которое является ложным для всех возможных комбинаций значений истинности утверждений компонентов, которые являются частью \ (S \).

То есть тавтология обязательно истинна при любых обстоятельствах, а противоречие обязательно ложно при любых обстоятельствах.

Проверка прогресса 2.4 (тавтологии и противоречия)

Для выписок \ (P \) и \ (Q \):

1. Используйте таблицу истинности, чтобы показать, что \ ((P \ vee \ urcorner P) \) является тавтологией.
2. Используйте таблицу истинности, чтобы показать, что \ ((P \ wedge \ urcorner P) \) противоречие.
3. Используйте таблицу истинности, чтобы определить, является ли \ (P \ to (P \ vee P) \) тавтологией, противоречием или нет.

Ответ

Добавьте сюда тексты. Не удаляйте сначала этот текст.

Упражнения к разделу 2.1

1. Предположим, Дейзи говорит: «Если не пойдет дождь, я буду играть в гольф». Позже вы узнаете, что шел дождь, но Дейзи все еще играла в гольф. Было ли заявление Дейзи правдой или ложью? Поддержите свой вывод.
2. Предположим, что \ (P \) и \ (Q \) — утверждения, для которых верно \ (P \ to Q \) и для которых верно \ (\ urcorner Q \).Какой вывод (если таковой имеется) можно сделать об истинности каждого из следующих утверждений?

   (a) \ (P \)
   (b) \ (P \ wedge Q \)
   (c) \ (P \ vee Q \)

3. Предположим, что \ (P \) и \ (Q \) — утверждения, для которых \ (P \ to Q \) ложно. Какой вывод (если таковой имеется) можно сделать об истинности каждого из следующих утверждений?

   (a) \ (\ urcorner P \ to Q \)
   (b) \ (Q \ to P \)
   (c) \ (P \ vee Q \)

4. Предположим, что \ (P \) и \ (Q \) — утверждения, для которых \ (Q \) ложно и \ (\ urcorner P \ to Q \) истинно (и неизвестно, если \ (R \) верно или неверно).Какой вывод (если таковой имеется) можно сделать об истинности каждого из следующих утверждений?

.