Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Высказывания

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     При построении алгебры логики мы использовали функциональный подход. Однако, можно было бы построить эту алгебру конструктивно. Сначала определить объекты изучения (высказывания), ввести операции над этими объектами и изучить их свойства. Дадим формальные определения.
     Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно (значение И или 1) или ложно (значение Л или 0) в конкретный момент времени. Например, «5-простое число», «нажата клавиша «Esc»» и т.д. При помощи связок «не», «и», «или», «если,… то», «если и только если» (им отвечают операции «¬», «&», «v», «→», «∼» соответственно) можно построить более сложные высказывания (предложения). Так строится алгебра высказываний.
     Для упрощения записи сложных высказываний вводится старшинство связок: «¬», «&», «v», «→», «∼», что помогает опустить лишние скобки.
     Простые высказывания назовем пропозициональными переменными.
     Введем понятие формулы.
     1. Пропозициональные переменные являются формулами.
     2. Если А, В формулы, то выражения ¬А, АВ, АvВ, А→В, А∼В являются формулами.
     3. Формулами являются только выражения построенные в соответствии с пп.1 и 2.
     Формула, принимающая значение И при всех значениях пропозициональных переменных называется тавтологией (или общезначимой), а формула, принимающая значение Л при всех значениях пропозициональных переменных называется противоречием (или невыполнимой).
     Описание свойств алгебры высказываний аналогично описанию соответствующих функций в булевой алгебре и мы их опускаем.

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru