Математическая ЛогикаРефераты >> Математика >> Математическая Логика
Опр: Предположим дана функция и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.
Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.
Предложение: Любую отмеченную грань можно вложить в максимальную грань.
Предложение:
(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)
Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.
Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.
Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.
Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.
3 Логические Исчисления.
3.1 Исчисления высказывания (ИВ).
3.1.1 Определения.
Опр: V – словом в алфавите А, называется любая конечная упорядоченная последовательность его букв.
Опр: Формативная последовательность слов – конечная последовательность слов и высказываний , если они имеют формат вида:
Опр: F – формулой ИВ, называется любое слово, входящее в какую-нибудь формативную последовательность.
Пример:
Опр: Аксиомы – специально выделенное подмножество формул.
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
Reg – правила вывода ИВ (некоторые правила преобразования первого слова в другое).
a – символ переменной
- произвольное слово ИВ (формула)
Отображение действует так, что на место каждого вхождения символа а , пишется слово .
Пример:
Правило modus ponens:
3.1.2 Формальный вывод.(простейшая модель доказательства теоремы)
Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид:
Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод. - выводимая формула ИВ.
Пример:
1) |
|
|
2) |
|
|
3) |
|
|
4) |
|
|
5) |
|
|
6) |
|
|
Правило одновременной подстановки.
Замечание: Если формула выводима, то выводима и
Возьмем формативную последовательность вывода и добавим в неё , получившаяся последовательность является формальным выводом.
(Если выводима то если , то выводима )
Теор: Если выводимая формула , то ( - различные символы переменных) выводима