2. Теорема Поста о функциональной полноте (Основная теорема о функциональной полноте).
Для того, чтобы система логических функций была функционально полной, необходимо и достаточно, чтобы она содержала
функцию, не сохраняющую нуль;
функцию, не сохраняющую единицу;
нелинейную функцию;
не самодвойственную функцию;
немонотонную функцию.
Вопросы для закрепления:
Что представляет собой полные системы логических функций? Приведите пример.
Приведите теорему Поста о функциональной полноте
Литература: Основная [1],[2]; дополнительная [1],[2]; Интернет ресурсы [1]-[4]
Тема 7 Логика и исчисление предикатов
Количество часов 1
Основные вопросы/план темы:
Логика и исчисление предикатов. Предикаты и кванторы.
Формулы логики предикатов. Равносильность формул, выполнимость , общезначимость.
Аксиомы исчисления предикатов.
Тезисы лекции*:
Предикат это сложное высказывание, в котором аргументы принимают значение из некоторой вещественной области , а значение самого высказывания принимает значение истинно или ложно.
Пример. Предикатом является высказывание – быть четным числом на множестве натуральных чисел:
- быть четным числом;
Предикаты могут быть одноместные - , двухместные - и многоместные -
Логические операции над предикатами.
Для предикатов выполнимы следующие операции:
Конъюнкция - это новый предикат, который принимает значение истинно при тех и только тех значениях из вещественной области , при которых оба предиката и истинны одновременно, и ложно во всех других случаях.
Достарыңызбен бөлісу: |
