Автор работы: Пользователь скрыл имя, 26 Ноября 2013 в 17:05, лекция
Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, то есть путем использования законов человеческого мышления. Изучение законов человеческого мышления является предметом логики.
Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384-322 г. до н.э.)- Он систематизировал известные до него сведения, и эта система стала впоследствии называться формальной или Аристотелевой логикой.
и
Первое из них есть дизъюнкция конъюнкции х, у, а второе высказывание есть импликация, посылкой которой является высказывание х, а заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z.
Формулой алгебры логики называется всякое сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических операций отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции.
Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В, С, ...
Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Если над формулой стоит знак отрицания, то скобки тоже опускаются.
Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний.
Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности.
Например, для формулы таблица истинности:
x |
y |
х&у |
||
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Легко видеть, что, если формула содержит п элементарных высказываний, то она принимает значений, состоящих из нулей и единиц, или, что то же, таблица содержит строк .
Определение. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.
Равносильность формул будем обозначать знаком , а запись А В означает, что формулы А и В равносильны.
Например, равносильны формулы:
Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.
Например, тожественно истинны формулы:
Формула А называется тождественно ложной, если она принимает значение О при всех значениях входящих в нее переменных.
Например, тождественно ложна формула:
Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно,
Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула - тавтология, то формулы А и В равносильны.
Как уже отмечалось, значение формулы алгебры логики полностью зависит от значений входящих в эту формулу высказываний. Поэтому формула алгебры логики является функцией входящих в нее элементарных высказываний.
Например, формула: является функцией трех переменных .
Определение. Функцией алгебры логики п переменных (или функцией Буля) называется функция п переменных, где каждая переменная принимает два значения: 0 в 1, и при этом функция может принимать только одно из двух значений: 0 или 1.
Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию.
Выясним, каково число функций п переменных. Очевидно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать строк. Следовательно, каждая функция п переменных принимает значений, состоящих из нулей и единиц. Таким образом, функция n переменных полностью определяется набором значений из нулей и единиц длины . Общее же число наборов, состоящих из нулей и единиц, длины равно . Значит, число различных функций алгебры логики n переменных равно .
В частности, различных функций одной переменной четыре, а различных функций двух переменных шестнадцать. Выпишем все функции алгебры логики одной и двух переменных.
Ясно, что аналитические выражения этих функций могут быть записаны следующим образом:
-единичная функция -сложение по модулю 2
-дизъюнкция -отрицание
-импликация функция сохранения второй переменной
- импликация -стрелка Пирса
-функция Шеффера
-функция сохранения первой
переменной
-эквивалентность - конъюнкция
-отрицание - нулевая функция
Для удобства представления логических функций существуют различные формы:
Дизъюнктивная нормальная форма (ДНФ) - это сумма произведений, образованных из переменных и их отрицаний. ДНФ не содержит скобок.
Например, формы_ - дизъюнктивная нормальная форма, a - нет.
Конъюнктивная нормальная форма (КНФ) - это произведение сумм, состоящих из переменных и их отрицаний.
Например, формы ( a +b)c, ab(c +b), , а- конъюнктивные нормальные формы.