Элементы алгебры логики
1. Алгебра высказываний (основные понятия, логические связки, таблицы истинности)
Математическая логика – анализ методом рассуждений, при этом в первую очередь исследуются формы рассуждений, а не их содержание. Логика – наука о законах и формах мышления.
Алгебра логики – раздел математической логики, в котором изучаются логические операции над выражениями.
Алгебра высказываний – учение о высказываниях. Изучает способы построения новых высказываний из уже имеющихся, закономерности различных способов сочетания высказываний. Изучает строение(форму,структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Высказывание – утверждение или повествовательное предложение, в отношении которого однозначно можно сказать истинно оно или ложно.
Простое высказывание – рассматривается как неделимое целое. Например, высказывания, не содержащие логических связок.
Сложное(составное) высказывание – высказывание, составленное из простых путем объединения их с помощью логических связок.
Логические связки - Частицы «НЕ», союзы «И», «ИЛИ», «ЕСЛИ…ТО», «ЛИБО…ЛИБО», «ТОГДА И ТОЛЬКО ТОГДА». Должны быть определены однозначно.
2. Булева алгебра(основные понятия, логические операции, таблицы истинности)
Универсальной Ω-алгеброй (или просто алгеброй)называется система G = (A, Ω),
Состоящая из некоторого непустого множества A (основное множество или
носитель алгебры) и множества определённых на A операций
Ω= { ω1k1, ω2k2, …ωnkn, …} (сигнатура алгебры), где ki– арность операции ωi,
ki ∈N, ar (ωi) = ki (функция арности), i= 1, 2, …, n, …
Операции из множества Ω называются основными операциями алгебры.
Булева алгебра состоит из: 1) из двух бинарных операций(дизъюнкция, конъюнкция) 2) одной унарной(инверсия) 3) двух нульярных (0 и 1). Для любых a,b,c ∈ A выполняется такая совокупность законов.
Понятие двоичной переменной и переключательной функции
Алфавит булевых переменных – каждая переменная принимает лишь одно из двух значений – 0 или 1.
Двоичная переменная (булева) – переменная, принимающая значения 0 или 1.
Булевы константы – 0 и 1
Переключательная функция (булева) – функция от любого конечного числа булевых переменных, принимающая значения либо 0, либо 1. С помощью этих функция записывается преобразование некоторым устройством входных сигналов в выходные:
Понятие набора двоичных переменных
Область определения булевой функции, зависящей от n аргументов, - это 2n элементов, называющиеся набором или кортежем, любой такой элемент – вектор длины n, каждый компонент которого равен 0 или 1.
Набор двоичных переменных – упорядоченная совокупность значений переменных (0 и 1)
Если булева функция двух переменных, тогда 2n – количество наборов. n – количество переменных.
(0,0), (0,1),(1,0),(1,1) – наборы.
Понятие о способах задания переключательных функций
1)Словесный
2)Аналитический. F(x1,x2,x3) = x1x2
3)Табличный
4)Графический
Булева функция однозначно задается перечислением всех наборов, на которых она равна 0, либо наборов, где она равна 1.