6.1 Высказывания и предикаты
Информатика, как было рассмотрено выше, изучает знаковые (алфавитные) совокупности. Алгебра – самый адекватный математический аппарат описания действий в них, исходя из этого алгебраический аппарат для описания информационных совокупностей неспециализированной природы, отвлеченно от их предметной направленности. Информационные процессы прекрасно формализуются посредством разных алгебраических структур.
Алгеброй A именуется некая совокупность определенных элементов X, с заданными над ними определенными операциями f (довольно часто определяемые по сходству с операциями умножения и сложения чисел), каковые удовлетворяют определенным особенностям – теоремам алгебры.
Операция f именуется n-местной, если она связывает n операндов (объектов – участников данной операции).
Совокупность операций алгебры A именуется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.
Утверждение (высказывательная форма) – главная единица, неделимая с позиций отражения смысла информации (семантики).
Высказывание – некое повествовательное утверждение, про которое возможно конкретно сообщить (сходу взглянуть на него), действительно оно либо ложно. Эти два значения всевозможных высказываний обозначаются истина и неправда, true и fаlse либо 1 и 0.
Переменная, значениями которой смогут быть только значения 1 либо 0, именуется логической переменной либо булевой переменной.
Высказывание должно быть конкретно подлинным либо конкретно фальшивым.
Разглядывая высказывания, мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их.
Пример. Выстроим из ниже заданных несложных высказываний составные, сложные высказывания, принимающие значение истина, неправда:
1. Зима – холодное время года.
2. Пальто – теплая одежда.
3. Камин – источник тепла.
Подлинным будет, к примеру, сложное высказывание: Зима – холодное время года и зимний период носят пальто, а фальшивым будет, к примеру, высказывание: Кое-какие ходят в пальто, исходя из этого на улице зима. Придумайте другие примеры.
Предикат – форма высказывания с логическими переменными (множество значений этих переменных в полной мере выяснено), имеющая суть при любых допустимых значениях этих переменных. Количество переменных в записи предиката именуется его местностью.
Простые высказывания либо предикаты не зависят от вторых высказываний либо предикатов (не разбиваемых на более простые), а сложные – зависит хотя бы от двух несложных.
Пример. Выражение х = у – предикат, х 5 – предикат, а 7 5 – высказывание. Утверждение Прекрасно не есть высказыванием, утверждение Оценка студента А по информатике – хорошая – простое высказывание, утверждение День назад была ясная погода, я был день назад на рыбалке – сложное высказывание, складывающееся из двух несложных.
Логической (булевой) функцией f(х) именуется некая функциональная зависимость, в которой довод х – логическая переменная с заданным множеством трансформаций довода, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.
Пример. Заданы предикаты вида р = число х делится нацело на 3 и q = у – сутки семь дней. Отыщем множество истинности предикатов р и q, в случае если
,
. Приобретаем, что.
Множество логических переменных
с определенными над ним операциями:
– отрицания либо инверсии (логическое «не»),
– логического сложения либо дизъюнкции (логическое «либо»),
– логического умножения либо конъюнкции (логическое «и») именуется алгеброй предикатов (и высказываний), в случае если эти операции удовлетворяют следующим теоремам:
1. Теорема двойного отрицания:
2. Теоремы переместительности операндов (относительно операций дизъюнкции и конъюнкции):
3. Теоремы конъюнкции операций и переместительности дизъюнкции (относительно операндов):
4. Теоремы однообразных операндов:
5. Теоремы поглощения (множителем – множителя-суммы либо слагаемым – слагаемого-произведения):
6. Теоремы распределения операции (дизъюнкции относительно конъюнкции и напротив):
7. Теоремы де Моргана (перенесения двоичной операции на операнды):
8. Теоремы нейтральности (взаимноинверсных множителей либо слагаемых):
9. Теорема существования единицы (истина, true, 1) и нуля (неправда, false, 0), причем,
Из этих теорем направляться последовательность нужных соотношений, к примеру:
;
.
Три базисные операции алгебры предикатов определяются таблицей их значений, поскольку в алгебре предикатов из-за дискретности значений логических функций довольно часто употребляется табличная форма задания функции. Булеву функцию n переменных возможно всецело выяснить таблицей из 2n строчков.
Итак, эти операции определяются совмещенной таблицей значений вида
Информатика. Алгебра логики: Таблицы истинности. Центр онлайн-обучения «Фоксфорд»
