Файл: Курс лекций по дисциплине Цифровая схемотехника для специальности.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 27.03.2024
Просмотров: 102
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
В. Сложное высказывание А
В (читается: А эквивалентно В) истинно тогда и только тогда, когда А истинно и В истинно либо А ложно и В ложно. В остальных случаях А В ложно. Эквиваленция задается следующей таблицей истинности.
Таким образом, сложное высказывание А В - это высказывание, в котором утверждается одновременно наличие или отсутствие ситуаций А и В. В классической логике и на естественном языке эквиваленция выражается словосочетаниями: «Если и только если . . , то . .» , «В том и только в том случае, когда. . , то . .» «Тогда и только тогда, когда ..». "Тогда и только тогда когда, А необходимо и достаточно для В". В соответствии с определением эквиваленции как двойной импликации, ее можно представить как конъюкцию двух импликаций: из А следует В, а из В следует А
Если сравнить приведенные таблицы истинности для эквиваленции и исключающей дизъюнкции, то видно, что одна является инверсией другой (исключающее ИЛИ есть инверсия эквиваленции и наоборот). Поэтому часто логическую связку исключающее ИЛИ так и называют неэквивалентность. Некоторые простейшие логические операции не являются независимыми, они могут быть выражены через систему других простейших логических операций.
Например, А
В = 
, то есть эквиваленция может быть выражена через строгую дизъюнкцию и отрицание. В свою очередь логическая операция исключающей дизъюнкции может быть выражена также через операции конъюнкции, дизъюнкции и отрицания следующим образом:
Как видим, все логические операции, за исключением операции отрицания, являются бинарными или двухместным» операциями, в которых обязательно присутствуют два операнда, а операция отрицания является унарной или одноместной логической операцией, которая действует на одно логическое высказывание или операнд.
2. Логические функции
С помощью логических операции и логических переменных можно составить различные логические функции.
Логические функции от любого количества логических переменных часто называют двоичными функциями (Булевыми функциями), так как при любом допустимом наборе логических переменных логические функции принимают только два значения - истина или ложь (1 или 0). Каждая логическая переменная также может принимать только два значения - истина или ложь (1 или 0). Логические переменные иногда называют пропозиционными переменными {от propositio - предложение, высказывание).
Кроме высказываний и логических операций в алгебре высказываний рассматриваются логические константы. Таких логических констант две - 1 и 0. Они отождествляются с абсолютной истиной и абсолютной ложью.
Введенных в рассмотрение логических операций вполне достаточно для того, чтобы из простейших высказываний образовывать любые сложные высказывания. Зная таблицы истинности логических операции, можно построить таблицу истинности для любого сложного высказывания.
Примерами составных высказываний могут быть следующие высказывания:
Приведенные выше высказывания называются формулами алгебры высказываний. Эти формулы состоят из простых высказываний А, В, знаков логических операций (
), а также скобок. Скобки, как и в обычной алгебре, указывают последовательность выполнения логических операций. При отсутствии скобок все логические операции выполняются в зависимости от их приоритетности. Иногда вместо приоритетности в алгебре логики говорят о "связывании" логических операций: первой всегда выполняется операция отрицания, затем конъюнкция
, дизъюнкция, исключающая дизъюнкция, импликация и эквиваленция. Все введенные выше логические операции приведены в порядке приоритета. Например, по приоритету конъюнкция выполняется раньше дизъюнкции. В этом случае говорят, что конъюнкция связывает сильнее, чем дизъюнкция.
Полнота системы логических функций. Некоторые введенные простейшие логические операции не являются независимыми, то есть они могут быть выражены с помощью других простейших логических операций. Эти вопросы, как и для любой алгебраической системы, относятся к проблеме так называемой полноты системы логических операций (функций).
Система логических функций называется полной, если все остальные логические функции могут быть представлены с помощью подстановок через функции этой выбранной системы. Минимальный набор логических операций, с помощью которых можно представить логические функции, называется базисом или базисной системой. Удаление из базисной системы хотя бы одной операции нарушает свойство полноты системы операции.
Система логических функций, использующая для представления всех логических функций только операции логического сложения, логического умножения и отрицания (
) является полной, так как любая логическая функция может быть представлена с помощью операций дизъюнкции, конъюнкции и отрицания. Но такая система не является базисной, так как из нее можно исключить операцию дизъюнкции либо конъюнкции и получатся две новые системы, которые также обладают свойством полноты и уже являются
базисными. Эти два базиса так и называют — конъюнктивный базис – {
} и
дизъюнктивный базис - {+,
}.
Оказывается, что существуют такие единичные логические операции, которые обладают свойством полноты и являются базисными, то есть с помощью одной такой логической операции можно выразить все остальные логические операции, а, следовательно, и все логические функции. Таким свойством обладают две элементарные бинарные логические операции: отрицание конъюнкции {антиконъюнкция) и отрицание дизъюнкции (антидизъюнкция), которые также часто называют по имени ученых-логиков, соответственно, штрих Шеффера (|) и строка Пирса — (
). Логические операции штрих Шеффера (|) и стрелка Пирса ( ) определяются следующим образом.
Отрицание от конъюнкции
Отрицание от конъюнкции (отрицание от логического умножения, антиконъюнкция) является операцией от двух логических переменных, которая принимает нулевое значение при единичных значениях переменных. Эту логическую операцию называют функцией Шеффера (штрих Шеффера) и ее обозначают А|В (читается: А штрих Шеффера В). Штрих Шеффера эквивалентен. А|В=
=
Операция штрих Шеффера – А|В задается следующей таблицей истинности.
Отрицание от дизъюнкции
Отрицание от дизъюнкции (отрицание от логического сложения, антидизъюнкция) является операцией от двух логических переменных, которая принимает единичное значение при нулевых значениях переменных. Эту логическую операцию также называется функцией Пирса (стрелка Пирса) и обозначают А В (читается "А стрелка Пирса В"). Стрелка Пирса эквивалентна A B=
Иногда эту операцию называют НИ-НИ - "неправильно, что А и неправильно, что В"). Операция стрелка Пирса - A В задается следующей таблицей истинности
В (читается: А эквивалентно В) истинно тогда и только тогда, когда А истинно и В истинно либо А ложно и В ложно. В остальных случаях А В ложно. Эквиваленция задается следующей таблицей истинности.| А | В | А В |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Таким образом, сложное высказывание А
В - это высказывание, в котором утверждается одновременно наличие или отсутствие ситуаций А и В. В классической логике и на естественном языке эквиваленция выражается словосочетаниями: «Если и только если . . , то . .» , «В том и только в том случае, когда. . , то . .» «Тогда и только тогда, когда ..». "Тогда и только тогда когда, А необходимо и достаточно для В". В соответствии с определением эквиваленции как двойной импликации, ее можно представить как конъюкцию двух импликаций: из А следует В, а из В следует А Если сравнить приведенные таблицы истинности для эквиваленции и исключающей дизъюнкции, то видно, что одна является инверсией другой (исключающее ИЛИ есть инверсия эквиваленции и наоборот). Поэтому часто логическую связку исключающее ИЛИ так и называют неэквивалентность. Некоторые простейшие логические операции не являются независимыми, они могут быть выражены через систему других простейших логических операций.
Например, А
В = , то есть эквиваленция может быть выражена через строгую дизъюнкцию и отрицание. В свою очередь логическая операция исключающей дизъюнкции может быть выражена также через операции конъюнкции, дизъюнкции и отрицания следующим образом:
Как видим, все логические операции, за исключением операции отрицания, являются бинарными или двухместным» операциями, в которых обязательно присутствуют два операнда, а операция отрицания является унарной или одноместной логической операцией, которая действует на одно логическое высказывание или операнд.
2. Логические функции
С помощью логических операции и логических переменных можно составить различные логические функции.
Логические функции от любого количества логических переменных часто называют двоичными функциями (Булевыми функциями), так как при любом допустимом наборе логических переменных логические функции принимают только два значения - истина или ложь (1 или 0). Каждая логическая переменная также может принимать только два значения - истина или ложь (1 или 0). Логические переменные иногда называют пропозиционными переменными {от propositio - предложение, высказывание).
Кроме высказываний и логических операций в алгебре высказываний рассматриваются логические константы. Таких логических констант две - 1 и 0. Они отождествляются с абсолютной истиной и абсолютной ложью.
Введенных в рассмотрение логических операций вполне достаточно для того, чтобы из простейших высказываний образовывать любые сложные высказывания. Зная таблицы истинности логических операции, можно построить таблицу истинности для любого сложного высказывания.
Примерами составных высказываний могут быть следующие высказывания:
Приведенные выше высказывания называются формулами алгебры высказываний. Эти формулы состоят из простых высказываний А, В, знаков логических операций (
), а также скобок. Скобки, как и в обычной алгебре, указывают последовательность выполнения логических операций. При отсутствии скобок все логические операции выполняются в зависимости от их приоритетности. Иногда вместо приоритетности в алгебре логики говорят о "связывании" логических операций: первой всегда выполняется операция отрицания, затем конъюнкция
, дизъюнкция, исключающая дизъюнкция, импликация и эквиваленция. Все введенные выше логические операции приведены в порядке приоритета. Например, по приоритету конъюнкция выполняется раньше дизъюнкции. В этом случае говорят, что конъюнкция связывает сильнее, чем дизъюнкция.
Полнота системы логических функций
Полнота системы логических функций. Некоторые введенные простейшие логические операции не являются независимыми, то есть они могут быть выражены с помощью других простейших логических операций. Эти вопросы, как и для любой алгебраической системы, относятся к проблеме так называемой полноты системы логических операций (функций).
Система логических функций называется полной, если все остальные логические функции могут быть представлены с помощью подстановок через функции этой выбранной системы. Минимальный набор логических операций, с помощью которых можно представить логические функции, называется базисом или базисной системой. Удаление из базисной системы хотя бы одной операции нарушает свойство полноты системы операции.
Система логических функций, использующая для представления всех логических функций только операции логического сложения, логического умножения и отрицания (
) является полной, так как любая логическая функция может быть представлена с помощью операций дизъюнкции, конъюнкции и отрицания. Но такая система не является базисной, так как из нее можно исключить операцию дизъюнкции либо конъюнкции и получатся две новые системы, которые также обладают свойством полноты и уже являютсябазисными. Эти два базиса так и называют — конъюнктивный базис – {
} идизъюнктивный базис - {+,
}.Оказывается, что существуют такие единичные логические операции, которые обладают свойством полноты и являются базисными, то есть с помощью одной такой логической операции можно выразить все остальные логические операции, а, следовательно, и все логические функции. Таким свойством обладают две элементарные бинарные логические операции: отрицание конъюнкции {антиконъюнкция) и отрицание дизъюнкции (антидизъюнкция), которые также часто называют по имени ученых-логиков, соответственно, штрих Шеффера (|) и строка Пирса — (
). Логические операции штрих Шеффера (|) и стрелка Пирса ( ) определяются следующим образом.Отрицание от конъюнкции
Отрицание от конъюнкции (отрицание от логического умножения, антиконъюнкция) является операцией от двух логических переменных, которая принимает нулевое значение при единичных значениях переменных. Эту логическую операцию называют функцией Шеффера (штрих Шеффера) и ее обозначают А|В (читается: А штрих Шеффера В). Штрих Шеффера эквивалентен. А|В=
= Операция штрих Шеффера – А|В задается следующей таблицей истинности.
| А | В | А|В |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Отрицание от дизъюнкции
Отрицание от дизъюнкции (отрицание от логического сложения, антидизъюнкция) является операцией от двух логических переменных, которая принимает единичное значение при нулевых значениях переменных. Эту логическую операцию также называется функцией Пирса (стрелка Пирса) и обозначают А
В (читается "А стрелка Пирса В"). Стрелка Пирса эквивалентна A B= Иногда эту операцию называют НИ-НИ - "неправильно, что А и неправильно, что В"). Операция стрелка Пирса - A
В задается следующей таблицей истинности| А | В | А В |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
