конспект Файрузов АТПб-20-2. Лекция Высказывания и предикаты
 Скачать 18.65 Kb.
|
|
Лекция: Высказывания и предикаты. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Операция f называется n-местной, если она связывает n операндов. Совокупность операций алгебры A называется ее сигнатурой , а совокупность элементов алгебры – носителем алгебры. Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "1" и "0". Рассматривая высказывания, мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их. Предикат – высказывательная форма с логическими переменными, имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью. Множество логических переменных с определенными над ним операциями: – отрицания или инверсии, – логического сложения или дизъюнкции , – логического умножения или конъюнкции называется алгеброй предикатов, если эти операции удовлетворяют следующим аксиомам: 1. Аксиома двойного отрицания: 2. Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции): 3. Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов): 4. Аксиомы одинаковых операндов: 5. Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения): 6. Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот): 7. Аксиомы де Моргана (перенесения бинарной операции на операнды): 8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых): 9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем, Из этих аксиом следует ряд полезных соотношений, например, Три базовые операции алгебры предикатов определяются таблицей их значений, так как в алгебре предикатов из-за дискретности значений логических функций часто используется табличная форма задания функции. Операции импликации и эквиваленции, хотя и являются часто используемыми, но не базовые, ибо они определяемы через три введенные выше базовые операции. Нетрудно определить их таблицы истинности. При выполнении логических операций в компьютере они сводятся к поразрядному сравнению битовых комбинаций. Эти операции достаточно быстро выполняемы, так как сводятся к выяснению совпадения или несовпадения битов. В логических формулах определено старшинство операций, например: скобки, отрицание, конъюнкция, дизъюнкция. Всегда истинные формулы называют тавтологиями . Логические функции эквивалентны, если совпадают их таблицы истинности, то есть совпадают области определения и значения, а также сами значения функции при одних и тех же наборах переменных из числа всех допустимых значений. Если это совпадение происходит на части множества допустимых значений, то формулы называются эквивалентными лишь на этой части. Задача упрощения логического выражения состоит в преобразовании его к более простому эквивалентному выражению. Логические функции позволяют эффективно решать так называемые инфологические задачи, доказывать утверждения. Информационно-логическая задача – задача, в которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача. Операции конъюнкции, дизъюнкции, отрицания алгебры высказываний – аналоги союзов "и", "или", приставки "не", используемых при выражении мысли человеком. Чтобы переложить на ЭВМ работы мыслительного характера, эти правила необходимо строго сформулировать, формализовать. Это позволяет осуществить алгебра логики. Приведем некоторые аксиомы логики – науки, изучающей методы доказательства и опровержения утверждений. 1. Аксиома исключения третьего : либо имеет место высказывание, либо его отрицание. 2. Аксиома противоречия : высказывания и его отрицание не могут иметь места одновременно. 3. Аксиома двойного отрицания : двукратное отрицание какого-либо утверждения равносильно исходному утверждению. 4. Аксиома тождества : всякое высказывание тождественно самому себе. Если высказывания x и y связаны друг с другом отношением , то говорят, что высказывание y следует из высказывания x; если множество истинности Х высказывания х содержит множество истинности Y высказывания y, то высказывание x – условие, высказывание y – заключение, а само соотношение – вывод. Доказательство формальных математических утверждений – последовательность корректных выводов, ведущих от условия к заключению. Алгебра логики помогает доказывать теоремы. Общий подход к доказательству теорем методом от противного, обратных и противоположных теорем можно формализовать с помощью алгебры логики. Лекция: Логические вентили, схемы, структуры. Логический вентиль – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана, открывая или закрывая путь сигналам. Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов. Они воспроизводят функции полупроводниковых схем. Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты. Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемые инвертором, дизъюнктором и конъюнктором. Логическая функция "инверсия", или отрицание, реализуется логической схемой, называемой инвертор. Принцип его работы можно условно описать следующим образом: если, например, "0" или "ложь" отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или "истина", которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт. Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт ("истина"), то на выходе инвертора будет сниматься 0 вольт, то есть "ложь". ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. Составное высказывание, которое может быть получено из элементарных высказываний путем применения логических операций, называется формулой алгебры логики. Порядок выполнения бинарных логических операций: сначала – конъюнкция, затем – дизъюнкция и в последнюю очередь – импликация и эквивалентность. Логические значения формулы алгебры логики могут быть описаны с помощью таблицы истинности. Формула, истинная при всех значениях входящих в нее переменных, называется тождественно истинной или тавтологией. Формула, ложная при всех значениях входящих в нен переменных, называется тождественно ложной или противоречием. Формула, истинная хотя бы на одном наборе значений входящих в нее переменных и не являющаяся тождественно истинной, называется выполнимой или опровержимой. РАВНОСИЛЬНЫЕ ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них элементарных высказываний. Равносильность формул 1 L и L2 обозначается как L1 L2 . Основные равносильности: 1. x & 0 0 , 7. x 0 x , 2. x &1 x , 8. x 1 1, 3. x & x x , 9. x x x , 4. x & x 0 , 10. x x 1, 5. x & ( y x) x , 11. x x . 6. x y & x x , Равносильности, выражающие одни логические операции через другие: 1. x & y x y , 4. x y x & y , 2. x & y x y , 5. x y x & y , 3. x y x y , 6. x y (x y) & ( y x). Равносильности, выражающие основные законы алгебры логики: 1. x & y y & x , 4. x y y x , 2. x & ( y & z) (x & y) & z, 5. x ( y z) (x y) z, 3. x & ( y z) x & y x & z , 6. x y & z (x y) & (x z). ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ Функцией алгебры логики ( , ,..., ) 1 2 n f x x x от n переменных n x , x ,..., x 1 2 называется функция, принимающая значения 1 или 0, аргументы которой также принимают значения 1 или 0. Любая формула алгебры логики есть функция алгебры логики, причем тождественно истинные и тождественно ложные формулы представляют собой постоянные функции. Любую функцию алгебры логики можно представить в виде формулы алгебры логики: f (x1 , x2 ,..., xn ) f (1,1,..., 1) & x1 & x2 & ... & xn f (1,1,..., 0) & x1 & x2 & ... & xn 1 & xn ... n n f (0, 0,..., 0) & x & x & ... & x & x 1 2 1 . Соответствующую функции ( , ,..., ) 1 2 n f x x x формулу алгебры логики можно получить с помощью таблицы истинности этой функции. Для этого для всех наборов значений переменных, на которых функция ( , ,..., ) 1 2 n f x x x принимает значение 1, записывается конъюнкция переменных высказываний, причем за член конъюнкции берется i x , если на указанном наборе значений переменных i x равно 1, и – i x , если на указанном наборе значений переменных i x равно 0. Дизъюнкция всех полученных таким образом конъюнкций и будет искомой формулой алгебры логики. |