Сведение к абсурду (Reductio ad Absurdum)

Если из того, что А не верно, следует, что В верно и не верно одновременно, то А верно

ùА →(В & ùB)

А Сведение к абсурду используется в методе доказательства, известном как доказательство от противного. Оно состоит в следующем

Предполагается, что истинным является отрицание того высказывания, которое необходимо доказать. Затем необходимо прийти к противоречию. Если это удается, то исходное утверждение доказано.

 

Алгебра логики. Бинарные логические операции. Существенные и несущественные (фиктивные) переменные. Функционально полные системы (базисы). Булева алгебра логики. Законы булевой алгебры. Примеры других алгебр логики.

 

Математическая логика состоит из двух разделов: логики высказываний и логики предикатов.

Логика высказываний может быть представлена двумя подходами: алгеброй логики (высказываний) и исчислением высказываний.

Алгебра, образованная множеством B={0,1} вместе со всеми возможными операциями на нем, называется алгеброй логики.

Алгебра логики как раздел математической логики изучает строение сложных логических высказываний (логических формул) и способы установления их истинности с помощью алгебраических методов.

Формулы алгебры логики состоят из

букв — логических (двоичных) переменных

знаков операций — логические операции (логические связки)

скобок

Каждая формула задает логическую функцию — функцию от логических переменных (т.е. принимающих значение 0,1), которая так же может принимать только два значения 0 и 1. Другими словами логическая функция имеет вид f(x1,x2,…xn): Bⁿ→B, где В множество состоящее из двух элементов В={0,1}.

Множество всех логических функций обозначается P ₂, множество всех логических функций n переменных — P ₂(n).

Число | P ₂(n)| различных функций n переменных равно числу различных двоичных векторов длины 2 ⁿ, т.е.

Бинарные функции (функции двух переменных)

Таблица истинности

Фиктивные переменные

Переменная x_i в функции f (x ₁,…, x_{i –1}, x_i, x_{i +1}, …, x_n) называется несущественной (или фиктивной), если f (x ₁,…, x_{i –1}, 1, x_{i +1}, …, x_n) = f (x ₁,…, x_{i –1}, 0, x_{i +1}, …, x_n) при любых значениях остальных переменных.

В этом случае f (x ₁,…, x_n) по существу зависит от n - 1 переменной, т.е. представляет собой функцию g (x 1,…, x_{i –1}, x_{i +1,} …, x_n) от 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 булевых функций f₀ и f₁,...,f_m называется функция F=f₀(g₁(x1,...,xm),...,g_n(x1,...,xm)), где каждая из функций g_i(x1,...,xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f₁,...,f_m.

 

Формулой называется выражение, описывающее эту суперпозицию.

Символы переменных, а также функции const_0 и const_1 считаются формулами глубины 0.

Пусть дано множество (конечное или бесконечное) исходных функций å ={ f ₁,..., f_m }. Любая формула F = f₀(g ₁,..., g_n), у которой g_i ÎS, n — количество аргументов f _0,, имеет глубину k=max(k₁…,k_n)+1, здесь k₁…,k_n глубины формул g ₁,..., g_n.

Формулы g ₁,..., g _n называются подформулами F. Функция f₀ называется внешней или главной операцией формулы 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.