Булевы функции одной переменной




Математическая логика

Лекция 3

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

Определение. Высказывание – повествовательное утверждение, которое либо истинно либо ложно (не то и другое одновременно).

Примеры высказываний: "Тише едешь – дальше будешь", "Париж – столица Франции". Но "Как бы чего не вышло" или "Миру – мир" не являются высказываниями.

Определение. Высказывание называется простым (элементарным), если оно рассматривается как одно неделимое целое.

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

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

Определение. Конъюнкцией ("и") высказываний P и Q называется высказывание, истинное тогда и только тогда, когда оба истинны. Обозначается P & Q.

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

P Q P & Q
л л л
л и л
и л л
и и и

Определение. Дизъюнкцией ("или") высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба ложны. Обозначается .

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

P Q
л л л
л и и
и л и
и и и

Определение. Отрицанием ("не") высказывания P называется высказывание, ложное тогда и только тогда, когда P истинно. Обозначается или .

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

P
л и
и л

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

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

P Q
л л и
л и и
и л л
и и и

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

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

P Q
л л и
л и л
и л л
и и и

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

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

P Q
л л л
л и и
и л и
и и л

Пропозициональные формулы

Рассмотрим алфавит , где , , .

Символы из называются переменными высказывания или пропозициональными переменными.

Символы из называются логическими связками.

Скобки из называются вспомогательными символами.

Определение. Пропозициональная формула определяется следующим образом:

1) пропозициональная переменная есть формула;

2) если P и Q – формулы, то Ø P, (P & Q), (PÚ Q),(P® Q),(PÅ Q),(P | Q), (P¯ Q) – формулы,

3) других формул нет.

При этом

а) внешние скобки у формул опускаются;

б) устанавливаются следующие приоритеты:

Ø – выполняется в первую очередь;

& во вторую очередь;

Ú, ®, Å, |, ¯ – в третью очередь.

Булевы функции. Таблицы истинности

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

Способы задания:

1) таблицами истинности; при этом 0 интерпретируется как "ложь", а 1 – как "истина";
2) пропозициональными формулами.

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

x y x & y xÚ y Ø x x® y XÅ y x~y
               
               
               
               

Булевы функции одной переменной

Обозначение Наименование
Константа 0
Тождественная
Отрицание
Константа 1


Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2020-11-01 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: