Сведение к абсурду (Reductio ad Absurdum)
Если из того, что А не верно, следует, что В верно и не верно одновременно, то А верно
ùА →( В & ùB )
АСведение к абсурду используется в методе доказательства, известном как доказательство от противного. Оно состоит в следующем
Предполагается, что истинным является отрицание того высказывания, которое необходимо доказать. Затем необходимо прийти к противоречию. Если это удается, то исходное утверждение доказано.
Алгебра логики. Бинарные логические операции. Существенные и несущественные (фиктивные) переменные. Функционально полные системы (базисы). Булева алгебра логики. Законы булевой алгебры. Примеры других алгебр логики.
Математическая логика состоит из двух разделов: логики высказываний и логики предикатов.
Логика высказываний может быть представлена двумя подходами: алгеброй логики (высказываний) и исчислением высказываний.
Алгебра, образованная множеством B={0,1} вместе со всеми возможными операциями на нем, называется алгеброй логики.
Алгебра логики как раздел математической логики изучает строение сложных логических высказываний (логических формул) и способы установления их истинности с помощью алгебраических методов.
Формулы алгебры логики состоят из
букв — логических (двоичных) переменных
знаков операций — логические операции (логические связки)
скобок
Каждая формула задает логическую функцию — функцию от логических переменных (т.е. принимающих значение 0,1), которая так же может принимать только два значения 0 и 1. Другими словами логическая функция имеет вид f(x1,x2,…xn): Bn→B, где В множество состоящее из двух элементов В={0,1}.
Множество всех логических функций обозначается P2, множество всех логических функций n переменных — P2(n).
Число |P2(n)| различных функций n переменных равно числу различных двоичных векторов длины 2n, т.е.
Бинарные функции (функции двух переменных)
Таблица истинности
Фиктивные переменные
Переменная xi в функции f(x1,…, xi–1, xi, xi+1, …, xn) называется несущественной (или фиктивной), если f(x1,…, xi–1, 1, xi+1, …, xn) = f(x1,…, xi–1, 0, xi+1, …, xn) при любых значениях остальных переменных.
В этом случае f(x1,…, xn) по существу зависит от n - 1 переменной, т.е. представляет собой функцию g(x1,…, xi–1, xi+1, …, xn) от n - 1 переменной.
Говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причем эти функции по определению считаются равными
Функционально полные системы (базисы)
Существуют наборы логических операций, с помощью которых можно выразить любые другие логические операции. Такие наборы называются функционально полными системами или базисами.
Примерыфункционально полных систем логических функций:
{o} (Функция Вебба),
{½} (штрих Шеффера);
{®, 0}, { ®, 1},
{ &, Å, 1}
и другие.
Наиболее изученным является базис {&, Ú, Ø}. Формулы, содержащие кроме переменных и скобок знаки этих функций называются булевыми.
Основные эквивалентные соотношения (законы) в булевой алгебре
ассоциативностей aÚ(bÚc)=(aÚb)Úc, aÙ(bÙc)=(aÙb)Ùc;
коммутативностей aÚb=bÚa, aÙb=bÙa;
дистрибутивностей aÙ(bÚc)=(aÙb)Ú(aÙc); aÚ(bÙc)=(aÚb)Ù(aÚc); идемпотентностей aÚa=a, aÙa=a;
двойного отрицания ØØa=a; законы нуля (лжи) aÚ0=a, aÙ0=0, aÙØa=0; законы единицы (истины) aÚ1=1, aÙ1=a, aÚØa=1. де-Моргана ØaÚØb=Ø(aÙb), ØaÙØb=Ø(aÚb);
противоречия aÙØа=0; исключенного третьего aÚØа=1
поглощения aÚaÙb=a, aÙ(aÚb)=a; склеивания aÙb Ú aÙØb =a, (aÚb)Ù(aÚØb)=a; обобщенное склеивание aÙc Ú bÙØc Ú aÙb = aÙc Ú bÙØc; a Ú ØaÙb = aÚb
Суперпозиция булевых функций и ее формула. Глубина формулы. Таблицы истинности для сложных формул. Эквивалентность формул. Тождественно истинная, тождественно ложная и выполнимая функция. Единичный и нулевой набор функции.
Суперпозицией F булевых функций f0 и f1,...,fmназывается функция F=f0(g1(x1,...,xm),...,gn(x1,...,xm)), где каждая из функций gi(x1, ...,xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,fm.
Формулой называется выражение, описывающее эту суперпозицию.
Символы переменных, а также функции const_0 и const_1 считаются формулами глубины 0.
Пусть дано множество (конечное или бесконечное) исходных функцийå={f1, ..., fm}. Любая формула F =f0(g1, ..., gn), у которой giÎS, n— количество аргументов f0,, имеет глубину k=max(k1…,kn)+1, здесь k1…,kn глубины формулg1, ..., gn.
Формулы g1, ..., gn называются подформулами F. Функция f0 называется внешней или главной операцией формулы F.
Пример: Глубина формул
Определить глубину формулы F= ((А→В)&C) ÚA.
Вначале выполняется f1= А→В. Глубина которой k1=max(0,0)+1=1
Следующей будет выполняться функция f2=f1&C. Функция f2 имеет глубину k2=max(k1,0)+1=max(1,0)+1=2
Далее выполнятся функция f3=f2ÚA, глубина которой k3=max(k2,0)+1=max(2,0)+1=3
Таким образом, глубина исходной формулы равна 3.