Автор: Пользователь скрыл имя, 11 Января 2012 в 16:09, доклад
«Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, чтобы облегчить сам процесс нашего мышления» (Лейбниц).
Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, то есть путем использования законов человеческого мышления. Изучение законов человеческого мышления является предметом логики.
Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384-322 г. до н.э.)- Он систематизировал известные до него сведения, и эта система стала впоследствии называться формальной или Аристотелевой логикой. Формальная логика просуществовала без серьезных изменений более двадцати столетий. Естественно, что развитие математики выявило недостаточность Аристотелевой логики и потребовало дальнейшего ее развития.
История развития математической логики.
Понятие высказывания
Логические операции над высказываниями
Формулы алгебры логики
Равносильные формулы алгебры логики
Алгебра Буля
Функции алгебры логики
Формы представления логических функций
Например, для функции:
СДНФ по таблице истинности может быть построена как
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 0 |
| 1 0 0 | 1 |
| 1 0 1 | 1 |
| 1 1 0 | 1 |
| 1 1 1 | 0 |
СДНФ_( F) = 000 + 010 + 100+ 101 +110_=
Теорема о КНФ. Всякая сложная логическая функция может быть сведена к КНФ.
Для того чтобы сделать эго, необходимо:
• записать булеву функцию в виде {+, -, -};
• с помощью законов де Моргана спустить черту отрицания до отдельных букв и по закону двойного отрицания уничтожить двойные черточки;
• с помощью второго закона дистрибутивности уничтожим все суммы произведений и проведем поглощение. Полученная форма удовлетворяет определению КНФ.
Если КНФ функции от n переменных в каждой своей дизъюнкции содержит все n переменных либо их отрицания, то это совершенная конъюнктивная нормальная форма. Каждая функция имеет одну-единственную СКНФ, и она может быть получена из таблицы истинности этой функции путем записи через знак логического умножения всех наборов переменных, на которых эта функция определена как ложная.
Например, для функции:
СКНФ по таблице истинности может быть построена как
| | |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 0 |
| 1 0 0 | 1 |
| 1 0 1 | 1 |
| 1 1 0 | 1 |
| 1 1 1 | 0 |
СКНФ=