Таблица истинности в логике – Таблица истинности — Википедия

Таблица истинности — Википедия

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 7 октября 2016; проверки требуют 23 правки. Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 7 октября 2016; проверки требуют 23 правки.

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

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

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

Таблицы истинности для основных двоичных логических функций[править | править код]

В программировании:

• Конъюнкция = AND = И = ∧{\displaystyle \land } = &
• Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
• Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
• Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !

Таблицы истинности для некоторых троичных логических функций[править | править код]

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
min(x,y)	2	1	0	1	1	0	0	0	0

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
max(x,y)	2	2	2	2	1	1	2	1	0

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
F2TN22310	0	0	0	0	2	2	0	2	1

• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966. — (Математическая логика и основания математики).

ru.wikipedia.org

Таблицы истинности, с формулами и примерами

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

   

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

Таблицы истинности для основных двоичных логических функций

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

Обозначение:

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

Обозначение:

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

Обозначение:

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

Обозначение:

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

Обозначение:

6. Штрих Шеффера – операция, отрицающая конъюнкцию, т.е. значение ложно тогда и только тогда, когда оба простых выражения истинны.

Обозначение:

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

Обозначение:

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

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

1. Инверсия
2. Конъюнкция
3. Дизъюнкция
4. Импликация
5. Эквиваленция
6. Штрих Шеффера
7. Стрелка Пирса

Для последних двух операций приоритет не определен.

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

Примеры решения задач

ru.solverbook.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

8.

 

 

 

 

 

 

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

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

2.  m_строк=2ⁿ, m=2²=4 строки.

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

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

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

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

 

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

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

 

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

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

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

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

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

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

 

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

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

 

 

 

 

 

 

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

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

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

 

X	Y	Z	F
0	0	0	1
0	0	1	0
0	1	0	1

 

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

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

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

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

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

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

Ответ: 3

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

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

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

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

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

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

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

Ответ: 3

mir-logiki.ru

Логические выражения и таблица истинности в примерах решения задач

Примеры решения задач “Логические выражения и таблица истинности”

Теория по этой теме по этой теме Пройти тестирование по этой теме Контрольная по этой теме

 №1.

Докажите, что А <=> В равносильно (A\/ ¬B) /\ (¬A\/ B)

 Для доказательства равносильности двух высказываний достаточно построить таблицу истинности для высказывания (A\/ ) /\ (\/ B) и сравнить ее с таблицей истинности эквивалентности:

А	В	¬B	A\/¬B	¬A	¬AVB	(A\/¬B) /\ (¬A \/B)
0	0	1	1	1	1	1
0	1	0	0	1	1	0
1	0	1	1	0	0	0
1	1	0	1	0	1	1

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

 

№2.

Укажите, какое логическое выражение равносильно выражению 

A /\ ¬ (¬B \/ C)

   1) ¬A \/ ¬B \/ ¬C

   2) A /\ ¬B /\ ¬C  

   3) A /\ B /\ ¬C 

   4) A /\ ¬B /\ C

Ответ:  3

№3.

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

1)A=>B<=> ¬А \/  B 

Ответ:

А	В	A=>B	¬А	A → B<=> ¬А	A → B<=> ¬А \/  B
0	0	1	1	1	1
0	1	1	0	0	1
1	0	0	0	1	1
1	1	1	0	0	1

2)F=A<=>B<=>(¬А \/  B) /\ (¬B\/  А)

Ответ:

 

 

 

 

 

№4.

Определите истинность следующего высказывания: «За окном светит солнце, и нет дождя».

Решение:

Нам дано сложное составное высказывание. Выделим из него простые высказывания:

А = «За окном светит солнце»

В = «За окном дождь»

 Составим логическую функцию, соответствующую данному высказыванию.

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

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

A	B	¬B	A /\ ¬B
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

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

 

№5.

Определите истинность следующего высказывания: «Гости смеялись, шутили и не расходились по домам».

Решение:

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

А = «Гости смеялись»

В = «Гости шутили»

С = «Гости расходились по домам»

Составим логическую функцию, соответствующую данному высказыванию.

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

Построим таблицу истинности для данной логической функции.

 

A	B	C	¬C	A /\ B/\¬C
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	0	0
1	0	0	1	0
1	0	1	0	0
1	1	0	1	1
1	1	1	0	0

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

 

№6.

На языке алгебры логики составьте истинное тождество, соответствующее заданному условию задачи:

Школьника, Миша, остававшийся в классе на перемене, был вызван к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчик ответили следующее: «Я не бил окно, и Коля тоже…»

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

Решение:

Пусть

А = «Окно разбил Миша»

В = «Окно разбил Коля»

Если Миша сказал чистую правду, то¬А /\ ¬В = 1.

Если в одной части заявления Миша соврал, а другое его высказывание истинно, то (¬А /\ В) \/ (А /\¬В) = 1

Если Миша оба факта исказил, то А /\ В = 1.

Ответ:

Истинное тождество, соответствующее условию задачи будет выглядеть так: ¬А /\ ¬В  \/¬А /\ В \/А /\ ¬ В \/ А /\ В = 1.

mir-logiki.ru

Логические функции алгебры логики: схемы и таблицы истинности

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

Введение в булевую алгебру

В 1854 году Джордж Буль провел исследование «законов мышления», которые основывались на упрощенной версии теории «групп» или «множеств», и из этого была выведена булевая алгебра.

Булева алгебра имеет дело, главным образом, с теорией, согласно которой логические операции и операции над множествами являются либо «ИСТИННЫМИ», либо «ЛОЖНЫМИ», но не обеими одновременно.

Например, A + A = A, а не 2A, как это было бы в обычной алгебре. Булева алгебра — это простой и эффективный способ представления действия переключения стандартных логических вентилей, а основные логические операторы, которые нас здесь интересуют, задаются операциями логических вентилей функций И , ИЛИ и НЕ.

Логическая функция «И» (умножение)

Функция логики И утверждает, что два или более события должны происходить вместе и одновременно, чтобы происходило выходное действие. Порядок, в котором происходят эти действия, не имеет значения, поскольку он не влияет на конечный результат. Например, & B = B & . В булевой алгебре функция логики И подчиняется коммутативному закону, который допускает изменение положения любой переменной.

Функция «И» представлена в электронике символом точки или полной остановки ( . ) Таким образом, 2-входное ( АВ ) «И» элемент имеет выходной термин, представленный логическим выражением A.B или просто AB.

Представление функции «И» на схеме

Здесь два переключателя A и B соединены вместе, образуя последовательную цепь. Поэтому в вышеупомянутой цепи оба выключателя A «И» B должны быть замкнуты (логика «1»), чтобы включить лампу. Другими словами, оба переключателя должны быть замкнуты или должны иметь логическую «1», чтобы лампа горела.

Тогда логический элемент этого типа (логический элемент «И» ) создает выход только тогда, когда все его входы истины. В терминах булевой алгебры вывод будет ИСТИНА, только когда все его входы ИСТИНА. В электрическом смысле логическая функция «И» равна последовательной цепи, как показано выше.

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

Таблица истинности для функции «И»

Логические «И» элементы доступны как стандартные пакеты ic, такие как общие TTL 74LS08 Четырехпозиционные 2-входные положительные элементы «И» (или эквивалент CMOS 4081), TTL 74LS11 Тройные 3-входные положительные элементы «И» или 74LS21 Двойные 4-входные положительные элементы «И». «И» ворота можно также «каскадировать» вместе для создания цепей с более чем 4 входами.

Логическая функция «ИЛИ» (сложение)

Функция логического «ИЛИ» заявляет, что выходное действие станет ИСТИНОЙ, если одно «ИЛИ» больше событий ИСТИНЫ, но порядок, в котором они происходят, не имеет значения, поскольку он не влияет на конечный результат.

Так , например, А + В = В + А . В булевой алгебре функция логического «ИЛИ» подчиняется коммутативному закону так же, как и для логической функции «И», что позволяет изменять положение любой переменной.

Логика или логическое выражение, данное для логического элемента «ИЛИ», является логическим выражением, которое обозначается знаком плюс, ( + ). Таким образом, 2-входной ( АВ ) Логический элемент «ИЛИ» имеет выход термин, представленный булевой выражением:  A + B = Q .

Представление функции «ИЛИ» на схеме

Здесь два переключателя А и B соединены параллельно и, либо переключатель A «ИЛИ» переключатель B может быть закрыт, чтобы включить лампу. Другими словами, выключатель может быть замкнут, либо быть на логике «1», чтобы лампа была включена.

Тогда этот тип логического элемента генерирует и выводит только тогда, когда присутствует «ЛЮБОЙ» из его входов, и в терминах Булевой алгебры выход будет ИСТИНА, если любой из его входов ИСТИНЕН. В электрическом смысле логическая функция «ИЛИ» равна параллельной цепи.

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

Таблица истинности для функции «ИЛИ»

Логические «ИЛИ» элементы доступны в виде стандартных пакетов ic, таких как общие TTL 74LS32 Четырехместные 2-входные положительные «ИЛИ» элементы. Как и в предыдущем логическом элементе «И», «ИЛИ» также может быть «каскадно» соединен для создания цепей с большим количеством входов, таких как системы охранной сигнализации (зона A или зона B или зона C и т.д.).

Логическая функция «НЕ» (отрицание)

Функция «Логическое НЕ» — это просто инвертор с одним входом, который изменяет вход логического уровня «1» на выход логического уровня «0» и наоборот.

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

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

Представление функции «НЕ» на схеме

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

Таблица истинности для функции «НЕ»

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

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

При проектировании логических схем вам может понадобиться только один или два инвертора в вашей конструкции, но если у вас нет места или денег для выделенного чипа инвертора, такого как 74LS04. Тогда вы можете легко заставить логику «НЕ» функционировать, используя любые запасные элементы «НЕ А» или «НЕ ИЛИ», просто соединяя их входы вместе, как показано ниже.

Логическая функция «НЕ И»

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

Функция логического «НЕ И» генерирует выход, только когда «ЛЮБЫЕ» из ее входов отсутствуют, и в терминах булевой алгебры выход будет ИСТИНА, только когда любой из ее входов ЛОЖЬ (0).

Представление функции «НЕ И» на схеме

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

Таблица истинности для функции «НЕ И»

Функция «НЕ И» обозначается вертикальной чертой или стрелкой вверх, например, логический B = A | Bили A ↑ B .

Логика «НЕ И» используется в качестве основных «строительных блоков», чтобы построить другие функции логического элемента и доступны в стандартных IC пакетов, такие как общий TTL — 74LS00 Четырехместный 2-входной «НЕ И» элемент, TTL — 74LS10 Тройной 3-входной «НЕ И» элемент или 74LS20 Двойной 4-х входной «НЕ И» элемент. Есть даже один чип 74LS30 с 8 входами «НЕ И» элемента.

Логическая функция «НЕ ИЛИ»

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

Чтобы создать вентиль «НЕ ИЛИ», функция «ИЛИ» и функция «НЕ» соединены вместе последовательно, и ее операция определяется булевым выражением как, A + B (с верхней чертой).

Функция логического «НЕ ИЛИ» генерирует и выводит только тогда, когда отсутствуют «ВСЕ» ее входы, и в терминах булевой алгебры выход будет ИСТИНА только тогда, когда все ее входы ЛОЖНЫ .

Представление функции «НЕ ИЛИ» на схеме

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

Таблица истинности для функции «НЕ ИЛИ»

Функция «НЕ ИЛИ» иногда известна как функция Пирса и обозначается стрелкой вниз, А «НЕ ИЛИ» B = A ↓ B.

Логика элемента «НЕ ИЛИ» доступны как стандартные IC пакетов, таких как TTL 74LS02 Четырехместный 2-входной элемент «НЕ ИЛИ», TTL 74LS27 Тройной 3-входной элемент «НЕ ИЛИ» или 74LS260 Двойной 5-входной элемент «НЕ ИЛИ».

meanders.ru

iMath Wiki — Алгебра логики. Основные логические операции и их таблицы истинности. Основные законы алгебры логики.

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

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

Алгебра логики является частью дискретной математики – раздела математики, изучающего свойства структур конечного характера.

Сама алгебра логики изучает свойства функций, у которых значения как аргументов, так и самих функций ограничены двумя значениями, например, \(\{0,1\}\).

Отцом алгебры логики считается английский математик Джордж Буль (1815-1864), поэтому алгебру логики иногда называют булевой алгеброй.

Долгое время алгебра логики была известна лишь узкому кругу специалистов, и только в 1938 году американский математик Клод Шеннон (1916-2001), стоявший у истоков современной информатики, показал, что алгебра логики применима для описания самых разных процессов, в том числе релейных и транзисторных схем.

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

Так, примерами высказываний могут служить такие фразы, как “сегодня идет дождь”, или “завтра я не пойду в институт”.

Определение истинности высказывания не всегда тривиально. Так, например:

Великая теорема Ферма

Для любого натурального числа \(n>2\) уравнение \[ a^n + b^n = c^n\] Не имеет решений в целых ненулевых числах \(a,\,b,\,c\)

Как известно, сформулированная Пьером Ферма в 1637 году, была окончательно доказана только в 1994.

Введем не совсем формальное, но достаточное для наших целей определение

Высказывание

это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности.

Это определение было предложено Аристотелем.

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

Элементарное высказывание

это такое высказывание, никакая часть которого не является высказыванием.

Следует заметить, что высказыванием в строгом смысле является только утверждение о конкретных объектах. Если речь идет о неких переменных, например, “x – рациональное число”, то мы говорим о неких функциях, имеющих значение “истина” или “ложь”. Такие функции называются предикатами.

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

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

Различные языковые связки, такие, как “не”, “если …, то …”, “или”, “и”, и т.п. позволяют строить из элементарных высказываний более сложные.

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

Введем некоторые из них.

Конъюнкция, или логическое умножение

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

Конъюнкция обозначается различными способами, в частности, амперсандом \(a \,\&\,b\), точкой \(a \cdot b\), или “крышкой” \(a \wedge b\), и соответствует языковой связке “и”. Мы будем в основном использовать амперсанд.

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

Дизъюнкция, или логическое сложение

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

Дизъюнкция соответствует союзу “или”, и обозначается плюсом \(a+b\), или “галочкой” \(a\vee b\). Мы будем использовать в основном второй вариант.

Таблица истинности дизъюнкции, по определению:

Строгая дизъюнкция, или сложение по модулю 2

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

Строгая дизъюнкция соответствует связке “либо …, либо …”, и обозначается плюсом в кружочке \(a\oplus b\), или треугольником \(a\vartriangle b\). Будем в основном пользоваться первым обозначением.

Таблица истинности, по определению:

Импликация

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

Импликация соответствует связке “если …, то …”, и обозначается стрелкой \(a \rightarrow b\), или \(a \Rightarrow b\)

Таблица истинности, по определению:

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

\[1 = 2\] \[2 = 1\]

Складывая эти равенства, получим очевидно истинный результат:

\[3=3.\]

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

Эквивалентность

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

Эквивалентность соответствует связке “тогда и только тогда, когда”, и обозначается \(a \Leftrightarrow b\), или \(a \equiv b\), или \(a \sim b\), или \(a \leftrightarrow b\). Будем в основном пользоваться первыми двумя обозначениями.

Таблица истинности, по определению:

Инверсия, или отрицание

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

Инверсия соответствует связке “не”, и обозначается \(\neg a\), или \(\;\overline{a}\;\), или \(!a\). Будем в основном пользоваться первыми двумя обозначениями.

Таблица истинности, по определению:

В заключение, таблица истинности основных логических операций:

0	0	1	0	0	0	1	1
0	1	1	0	1	1	1	0
1	0	0	0	1	1	0	0
1	1	0	1	1	0	1	1

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

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

Логическая переменная

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

Логическая формула

любая переменная, а так же любая из констант “0” (“ложь”) и “1” (“истина”)

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

Эквивалентные формулы

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

Существуют следующие “законы” алгебры логики, определяющие некий набор эквивалентных формул:

Законы коммутативности

\[x \,\&\,y = y \,\&\,x\] \[x \vee y = y\vee x\]

Законы ассоциативности

\[ (x \,\&\,y) \,\&\,z = x \,\&\,(y \,\&\,z)\] \[ (x \vee y) \vee z = x \vee(y \vee z)\]

Законы поглощения

\[x\vee 0 = x\] \[x\,\&\,1 = x\]

Законы дистрибутивности

\[ x\,\&\,(y\vee z) = (x\,\&\,y) \vee(x\,\&\,z)\] \[ x\vee(y\,\&\,z) = (x \vee y) \,\&\,(x\vee z)\]

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

\[ x \,\&\,\;\overline{x}\; = 0\]

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

\[ x \vee\;\overline{x}\; = 1\]

Закон равносильности

\[ x \,\&\,x = x\] \[ x \vee x = x \]

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

\[\;\overline{\;\overline{x}\;}\; = x \]

Законы де Моргана

\[ \;\overline{x\,\&\,y}\; = \;\overline{x}\; \vee\;\overline{y}\; \] \[ \;\overline{x\vee y}\; = \;\overline{x}\; \,\&\,\;\overline{y}\; \]

Законы поглощения

\[ x\vee(x\,\&\,y) = x\] \[ x\,\&\,(x\vee y) = x\]

Все перечисленные законы элементарно доказываются составлением таблиц истинности.

Например, первый закон де Моргана:

0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

3 и 6 столбец одинаковы, следовательно, соответствующие формулы эквивалентны.

Введем еще одно определение

Тавтология

логическая формула, которая всегда истинна.

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

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

Итак, формальный способ решения логических задач:

1. Из условий задачи выделяются простые высказывания и обозначаются как логические переменные.
2. Условия задачи записываются в виде логических формул
3. Составляется единое логическое выражение, соответствующее условию задачи. По условию задачи оно является истинным.
4. Полученное выражение упрощается, либо составляется таблица истинности для него (либо и то, и другое)
5. Выбирается решение задачи (случаи, когда условие истинно)
6. Решение формулируется в исходных терминах задачи.

Пример: (источник)

На весеннем фестивале, четыре садовника показывали выращенные ими розы.

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

Известно, что

• У первого была желтая роза
• У второго не было красной розы
• У третьего была синяя роза, но не было зеленой
• У одного из садовников с зеленой розой не было красной
• Ни у одного из садовников с желтой розой не было зеленой
• Ни у кого нет роз двух одинаковых цветов

Введем переменные, в которых название переменной соответствует цвету, а индекс – садовнику (номеру). Это автоматически учитывает условие “Ни у кого нет роз двух одинаковых цветов”. Тогда условия задачи запишутся в виде:

• \(y_1\)
• \(\;\overline{r_2}\;\)
• \(b_3 \,\&\,\;\overline{g_3}\;\)
• \((g_1\rightarrow\;\overline{r_1}\;) \oplus(g_2\rightarrow\;\overline{r_2}\;)\oplus(g_3\rightarrow\;\overline{r_3}\;)\oplus(g_4\rightarrow\;\overline{r_4}\;)\)
• \((y_1\rightarrow\;\overline{g_1}\;) \,\&\,(y_2\rightarrow\;\overline{g_2}\;)\,\&\,(y_3\rightarrow\;\overline{g_3}\;)\,\&\,(y_4\rightarrow\;\overline{g_4}\;)\)

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

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

Рассматривая последнее условие:

\((y_1\rightarrow\;\overline{g_1}\;) (y_2\rightarrow\;\overline{g_2}\;)(y_3\rightarrow\;\overline{g_3}\;)(y_4\rightarrow\;\overline{g_4}\;)\)

Первая импликация истинна, только если \(\;\overline{g_1}\;\) истинно. Предпоследняя импликация истинна всегда, \(\;\overline{g_3}\;\). Можем переписать в виде:

\(y_1 \;\overline{g_1}\; (y_2\rightarrow\;\overline{g_2}\;) (y_4\rightarrow\;\overline{g_4}\;)\)

Рассмотрим предпоследнее условие

\[ (g_1 \rightarrow\;\overline{r_1}\;) \oplus(g_2 \rightarrow\;\overline{r_2}\;) \oplus(g_3 \rightarrow\;\overline{r_3}\;) \oplus(g_4 \rightarrow\;\overline{r_4}\;) \]

Первая импликация всегда истинна, поскольку \(\;\overline{g_1}\;\), вторая всегда истинна, поскольку \(\;\overline{r_2}\;\), третья всегда истинна, поскольку \(\;\overline{g_3}\;\). Получаем:

\[ 1 \oplus 1 \oplus 1 \oplus(g_4 \rightarrow\;\overline{r_4}\;) \]

\[ 1 \oplus(g_4 \rightarrow\;\overline{r_4}\;) \]

Легко показать, что \(1 \oplus x = \;\overline{x}\;\). Тогда условие принимает вид

\[ \;\overline{g_4 \rightarrow\;\overline{r_4}\;}\; \]

Импликацию можно представить в виде \(x \rightarrow y = \;\overline{x}\; \vee y\)

Применяя закон де Моргана,

\[ r_4 g_4 \]

Записывая все условия вместе:

\[ y_1 \;\overline{g_1}\; \;\overline{r_2}\; (\;\overline{y_2}\; \vee\;\overline{g_2}\;) (\;\overline{y_4}\; \vee\;\overline{g_4}\;) b_3 \;\overline{g_3}\; g_4 r_4 \]

Учитывая \(g_4 (\;\overline{y_4}\; \vee\;\overline{g_4}\;) = g_4 \;\overline{y_4}\;\),

\[ y_1 \;\overline{g_1}\; \;\overline{r_2}\; (\;\overline{y_2}\; \vee\;\overline{g_2}\;) b_3 \;\overline{g_3}\; \;\overline{y_4}\; g_4 r_4 \]

Известно, что зеленые розы должны быть у двух садовников:

\[ \;\overline{g_1}\; \;\overline{g_2}\; g_3 g_4 \vee\;\overline{g_1}\; g_2 \;\overline{g_3}\; g_4 \vee\;\overline{g_1}\; g_2 g_3 \;\overline{g_4}\; \vee g_1 \;\overline{g_2}\; \;\overline{g_3}\; g_4 \vee g_1 \;\overline{g_2}\; g_3 \;\overline{g_4}\; \vee g_1 g_2 \;\overline{g_3}\; \;\overline{g_4}\; \]

А так как \(\;\overline{g_3}\;\) и \(\;\overline{g_1}\;\)

\[ \;\overline{g_1}\; g_2 \;\overline{g_3}\; g_4 \]

Получаем \(g_2\), тогда \(g_2 (\;\overline{y_2}\; \vee\;\overline{g_2}\;) = g_2 \;\overline{y_2}\;\)

Аналогично для желтых:

\[ y_1 \;\overline{y_2}\; y_3 \;\overline{y_4}\; \]

Получаем \(y_3\). Поскольку \(y_3 b_3\), можно утверждать \(\;\overline{r_3}\; \;\overline{g_3}\;\)

Для красных тогда:

\[ r_1 \;\overline{r_2}\; \;\overline{r_3}\; r_4 \]

Получаем \(r_1\). Поскольку \(r_1 y_1\), можем утверждать \(\;\overline{b_1}\; \;\overline{g_1}\;\)

Для синих:

\[ \;\overline{b_1}\; b_2 b_3 \;\overline{b_4}\; \]

Получаем \(b_2\).

Итого

\[ y_1 r_1 g_2 b_2 b_3 y_3 g_4 r_4 \]

wiki.livid.pp.ru

Таблица истинности — это… Что такое Таблица истинности?

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

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

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

Таблицы истинности для основных двоичных логических функций

Таблицы истинности для некоторых троичных логических функций

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
Минимум	2	1	0	1	1	0	0	0	0

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
Максимум Минус.	2	2	2	2	1	1	2	1	0

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
Webb(x,y)	0	0	0	0	2	2	0	2	1

См. также

Примечания

Литература

• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966. — (Математическая логика и основания математики).

Ссылки

dic.academic.ru