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

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

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

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

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

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

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

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

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

Рисунок 1.

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

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

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

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

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

Рисунок 2.

Пример 1

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

Решение:

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

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

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

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

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

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

Рисунок 3.

Пример 2

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

Решение:

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

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

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

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

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

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

отрицание ($\bar{C}$);
дизъюнкция, т.к. она находится в скобках ($A \vee B$);
конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
дизъюнкция ($A \vee C$);
конъюнкция ($(A\vee C)\bigwedge B$);
отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);
дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).

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

Отрицание (инверсия), от латинского inversio -переворачиваю:

Соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО;

Обозначение: не A, A, -A;

таблица истинности:

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

Пример: A = {На улице идет снег}.

A={Не верно, что на улице идет снег}

A={На улице не идет снег};

Логическое сложение (дизъюнкция), от латинского disjunctio - различаю:

Соответствует союзу ИЛИ;

Обозначение: +, или, or, V;

Таблица истинности:

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

Пример: F={На улице светит солнце или дует сильный ветер};

Логическое умножение (конъюкция), от латинского conjunctio -связываю:

Соответствует союзу И

(в естественном языке: и А, и В, как А, так и В,А вместе с В,А, не смотря на В, А, в то время как В);

Обозначение: Ч, , &, и, ^, and;

Таблица истинности:

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

Пример: F={На улице светит солнце и дует сильный ветер};

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

2) Таблица истинности - это таблица, описывающая логическую функцию.

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

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

Конъю́нкция- логическая операция, по своему применению максимально приближённая к союзу "и".логи́ческое умноже́ние, иногда просто "И".

Дизъю́нкция-логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». логи́ческое сложе́ние, иногда просто «ИЛИ».

Импликация - бинарная логическая связка, по своему применению приближенная к союзам «если…то…».Импликация записывается как посылка следствие; применяются также стрелки другой формы и направленные в другую сторону (остриё всегда указывает на следствие).

Эквивале́нция (или эквивале́нтность) - двуместная логическая операция. Обычно обозначается символом ≡ или ↔.

7 . Логические выражения, таблицы истинности логических выражений.

Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)

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

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

Логическое умножение КОНЪЮНКЦИЯ - это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

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

Логическое отрицание: ИНВЕРСИЯ - если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным/ Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО

Логическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом "следовательно" и выражается словами ЕСЛИ … , ТО …

Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности"

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

1. инверсия

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

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

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

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

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

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

Количество строк = 2n + две строки для заголовка (n - количество простых высказываний)

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

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

ПРИМЕР: составить таблицу истинности сложного логического выражения D = неA & (B+C)

А,В, С - три простых высказывания, поэтому:

количество строк = 23 +2 = 10 (n=3, т.к. на входе три элеманта А, В, С)

количество столбцов: 1) А

4) не A это инверсия А (обозначим Е)

5) B + C это операция дизъюнкции (обозначим F)

6) D = неA & (B+C), т.е. D = E & F это операция конъюнкции

А В С E = не А (не 1) F = В+С (2+3) D = E&F (4*5)

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

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

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

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

1. инверсия;

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

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

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

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

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

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

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

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

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

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

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

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

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

D = А & ( B V C )

Решение:

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

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

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

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

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

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

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

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

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

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

font-size:12.0pt">Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z (X ,Y ):

font-size:12.0pt">1 .

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

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

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

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

1. инверсия;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

D = А & (B  C) .

Решение: 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

A	B	C	B V C

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

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

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

Любое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина . Ложь обозначается нулём, а истина - единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики.

Отрицание

Отрицание и инверсия - самое простое логическое преобразование. Ему соответствует частица "не." Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то "не А" - ложно. Например, утверждение "прямой угол - это угол, равный девяносто градусов" - истина. Тогда его отрицание "прямой угол не равен девяноста градусам" - ложь.

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

Дизъюнкция

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

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

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

Таблица значений исключающего или

Импликация и эквивалентность

Импликация представляет собой следствие и грамматически может быть выражена как "из А следует Б". Здесь утверждение А будет называться предпосылкой, а Б - следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки - истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.

В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А - "точка О - экстремум непрерывной функции", утверждение Б - "производная непрерывной функции в точке О обращается в ноль". Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.

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

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

В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А - "Точка О является точкой экстремума непрерывной функции", утверждение Б - "В точке О производная функции обращается в ноль и меняет знак". Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А. Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: "производная в точке О обращается в ноль" и "производная в точке О меняет знак".

Прочие логические функции

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

Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
Стрелка Пирса представляет сбой отрицание дизъюнкции.

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

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

Разбить выражение на простые утверждения и обозначить каждое из них как переменную.
Определить логические преобразования.
Выявить порядок действий этих преобразований.
Сосчитать строки в будущей таблице. Их количество равно два в степени N, где N - число переменных, плюс одна строка для шапки таблицы.
Определить число столбцов. Оно равно сумме количества переменных и количества действий. Можно представлять результат каждого действия в виде новой переменной, если так будет понятней.
Шапка заполняется последовательно, сначала все переменные, потом результаты действий в порядке их выполнения.
Заполнение таблицы надо начать с первой переменной. Для неё количество строк делится пополам. Одна половина заполняется нулями, вторая - единицами.
Для каждой следующей переменной нули и единицы чередуются вдвое чаще.
Таким образом заполняются все столбцы с переменными и для последней переменной значение меняется в каждой строке.
Потом последовательно заполняются результаты всех действий.

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

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

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

Примеры

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

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

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

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

А	Б	А и Б	не (А и Б)
Л	Л	Л	И
Л	И	Л	И
И	Л	Л	И
И	И	И	Л

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

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

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

А	Б	не А	не Б	не А и не Б
Л	Л	И	И	И
Л	И	И	Л	Л
И	Л	Л	И	И
И	И	Л	Л	Л

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

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

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

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

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