Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Объекты алгебры высказываний.
• Объектами алгебры высказыванийявляются высказывания. • Высказыванием называется повествовательное предложение, о котором можно сказать Истинно оно или Ложно. Высказывания: простые и сложные Простые высказывания • Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием (суждением). Например, предложение «Луна – спутник Земли» есть простое высказывание, предложения «Не сорить! » «Не жевать! » «Не болтать! » не являются высказываниями. • 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
Инверсия (Логическое отрицание) • Логическое отрицание делает истинное высказывание ложным и наоборот ложное истинным. • 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) |
Последнее изменение этой страницы: 2017-03-14; Просмотров: 498; Нарушение авторского права страницы