Объекты алгебры высказываний.

• Объектами алгебры высказыванийявляются высказывания.

• Высказыванием называется повествовательное предложение, о котором можно сказать Истинно оно или Ложно.

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

Простые высказывания

• Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием (суждением). Например, предложение «Луна – спутник Земли» есть простое высказывание, предложения «Не сорить! » «Не жевать! » «Не болтать! » не являются высказываниями.

• 5 – простое число. Это высказывание – истинно.

• 7 – чётное число – ложно.

• Истинному высказыванию ставится в соответствие 1, а ложному - 0.

Составные высказывания

 

 

• Высказывания обозначаются большими буквами латинского алфавита (имена логических (булевых) переменных, которые могут принимать только 2 значения). Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.

• Тогда к ним можно применять определённые правила, как к двоичным переменным.

• Если 2 или более простых высказывания связаны между собой логической операцией, то получается сложное высказывание (составное) (которое также принимают значения 0 или 1)

• Как и в других алгебрах, в алгебре высказываний над ее объектами (высказываниями) определены действия, при выполнении которых получают новые высказывания. Объединение двух высказываний в одно при помощи «И» называется операцией логического умножения. Полученное таким образом высказывание называется логическимпроизведением.

Например: сейчас самое время пообедать, а я сижу на Информатике

 

В.33 ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Для высказываний определены следующие операции:

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

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

• сложение по модулю два ( XOr, исключающее ИЛИ)

• стрелка Пи́ рса («антидизъюнкция»)

• штрих Ше́ ффера («антиконъюнкция»)

• импликация от Y к X,

• импликация от X к Y,

• инверсии импликаций,

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

• Отрицание (НЕ)

 

• Истинность или ложность сложных высказываний определяется с помощью таблиц истинности (для каждого своя), которая определяет истинность или ложность сложного высказывания при всех возможных комбинациях входящих в него простых высказываний (логических переменных, (булевых переменных), которые принимают одно из двух возможных значений: True/ False):

 

 

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

• f1 (x, y) — конъюнкция ( f1 (x, y) = x& y = x.y = xÙ y = min(x, у)), AND

• f2 (x, y) — дизъюнкция ( f2 (x, y) = x||y=xÚ y = max(x, y)), OR

• f3 (x, y) — эквивалентность ( f3 (x, y) = x~y = xº y = x«y),

• f4 (x, y) — сумма по модулю два ( f4 (x, y) = xÅ y), XOr

• f5 (x, y) — импликация от y к x ( f5 (x, y) = xy = xÌ y),

• f6 (x, y) — импликация от x к y ( f6 (x, y) = x→ y = xÉ y),

• f7 (x, y) — стрелка Пи́ рса = функция Да́ ггера = функция Ве́ бба («антидизъюнкция») ( f7 (x, y) = x¯ y).

• f8 (x, y) — штрих Ше́ ффера («антиконъюнкция») ( f8 (x, y) = x/y),

• f9 (x, y), f10 (x, y) — инверсии импликаций f5 и f6,

Дизъюнкция (Логическое ИЛИ; OR) (логическое сложение Ú; +; ||)

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

Таблица истинности для ИЛИ

• AÚ B=0, Если А=В=0;

• AÚ B=1, Если А=1 или В=1 или А=В=1

Конъюнкция (Логическое И; AND) (логическое умножение Ù; .; & )

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

 

Таблица истинности для И

• АÙ В = 1, если А=В=1;

• А & B = 0, если A=0 или В=0 или А=В=0

 

 

Инверсия (Логическое отрицание)
Not, НЕ, !, Ø,

• Логическое отрицание делает истинное высказывание ложным и наоборот ложное истинным.

• Y=1, если A=0;

• Y=0, если A=1; Таблица истинности:

 

 

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

 

всевозможные значения для высказывания Y можно записать в виде таблицы истинности,

 

Функции И ИЛИ НЕ являются БАЗОВЫМИ, к ним м.б. сведены все логические функции путём логических преобразований.

В34. Логические функции (продолжение)

Сложение по модулю 2 (XOR, Å )

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

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

Таблица истинности для XOR

• Y=1, если A¹ B

• Y=0, если A=B

Штрих Шеффера Y=A/B

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

 

 

 

Таблица истинности функции «Штрих Шеффера»

• Y=0, если А=В=1;

• Y=1, если A=1 B=0; A=0 B=1; A=B=0;

 

 

 

Логическая функция «Стрелка Пирса»

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

 

 

 

Таблица истинности функции «Стрелка Пирса»

• Y=1, если А=В=0;

• Y=0, если A=1 B=0; A=0 B=1; A=B=1;

 

 

В.35 Логические функции (продолжение)
ИМПЛИКАЦИЯ (Логическое следование)

• Импликация от А к В «Если А, то В» А → В. Сложное высказывание, образованное с помощью операции логического следования (импликации) ложно тогда и только тогда, когда из истинной предпосылки (1-го высказывания) следует ложный вывод (2-е высказывание). (Пример: 1. Если число делится на 10, то оно делится и на 2 - Истина; 2. Если число делится на 10, то оно делится и на 3 – Ложь)

Таблица истинности функции «Логическое следование» А → В

• Y=0, если А=1, то В=0

• Y=1, если А= В=0; А=В=1; А=0 В=1;

 

 

 

• Импликация А → В равносильна логическому выражению:

 

 

Импликация от В к А (В → А)

• Импликация от А к В «Если В, то А» В → А. Сложное высказывание, образованное с помощью операции логического следования (импликации) ложно тогда и только тогда, когда для истинного следствия (2-го высказывания) была ложная предпосылка (1-е высказывание).

Таблица истинности функции Импликации А В

• Y=0, В=1 А=0;

• Y=1, если А= В=0; А=В=1; А=1 В=0;

Импликация А В равносильна логическому выражению:

 

Логическая функция «Эквивалентность»

• Логическое равенство объединяет 2 высказывания в одно сложное с помощью оборота «тогда и только тогда». Сложное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания либо истинны, либо ложны.

• Пример: Студенты могут сдавать сессию. Зачёты получены. Студенты могут сдавать сессию тогда и только тогда, когда получены все зачёты.

Таблица истинности функции Эквивалентности А « В (А~B)

• Y=1, если А=В (А=В=1 или А=В=0)

• Y=0, если А¹ В (А=1 В=0 или А=0 В=1)

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: