Элементы математической логики

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

Высказывания
простые
сложные
5 > 3
истина
x * x < 0
ложь
Получаются путём объединения простых высказываний связками-союзами И, ИЛИ, НЕ.
При этом значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок
Значение истинности или ложности простого высказывания определяется однозначно!
(x >2) and (x < -5)

Алгебра логики (алгебра высказываний, булева алгебра) – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Простые высказывания называют в алгебре логики логическими переменными и обозначают буквами латинского алфавита.
Сложные высказывания называют логическими функциями (или логическими выражениями).
Логические переменные и функции определены на множестве двух значений {0,1} или {true, false}

Логические операции
Инверсия
- логическое отрицание
- логическое умножение
a и b a ∧ b a . b a AND b
Конъюнкция

Дизъюнкция (нестрогая)
- логическое сложение
a или b a ∨ b a or b

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

Логические элементы
Инвертор
Конъюнктор
Схема «И»

Логические элементы
Дизъюнктор
Схемы «И», «ИЛИ», «НЕ» образуют функционально полную систему, т.е. с помощью этих схем может быть построено любое устройство ЭВМ.
1

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

Задача 1.
Дана структурная формула: F(X,Y)= (X v Y) & X
Постройте соответствующую ей функциональную схему.
Решение:
Проверить , что эта функциональная схема соответствует заданной структурной формуле, можно, сравнив таблицы истинности для той и другой.
1
2
3
4

Таблица истинности для формулы
F(X,Y)= (X v Y) & X

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

Задача 2
Определите структурную формулу по заданной функциональной схеме:

ЕГЭ 2006
A9
Для какого из указанных значений числа X истинно высказывание:
(X>4) \/ ((X>1) ->(X>4))?
1)1 2)2 3)3 4)4
A10
Какое логическое выражение равносильно выражению
¬ (¬A \/ B) \/ ¬C?
1)(A /\ ¬B) \/ ¬C 2)¬A \/ B \/ ¬C 3)A \/ ¬B \/ ¬C 4)(¬A /\ B) \/ ¬C
A11
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности :
Какое выражение соответствует F?
1)¬X \/ ¬Y \/ ¬Z 2)X /\ ¬Y /\ ¬Z 3)X \/ Y \/ Z 4)X /\ Y /\ Z

ЕГЭ 2007
A9
Для какого числа X истинно высказывание
((X>3) \/(X<3)) –> (X<1)
1)1 2)2 3)3 4)4
A10
Какое логическое выражение равносильно выражению ¬ (A /\ B) /\ ¬C?
1)¬A \/ B \/ ¬C 2)(¬A \/ ¬B) /\ ¬C 3)(¬A \/ ¬B) /\ C 4)¬A /\ ¬B /\ ¬C
A11
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
1)¬X \/ Y \/ ¬Z 2)X /\ Y /\ ¬Z 3)¬X /\ ¬Y /\ Z 4)X \/ ¬Y \/ Z