Глоссарий по математической логике

№ п/п

Новые понятия

Содержание

1

Булевая алгебра

Непустое множество A с двумя бинарными операциями  (аналог конъюнкции),  (аналог дизъюнкции),унарной операцией  (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина)

2

Булевый базис

Набор трех логических функций: НЕ, И, ИЛИ называют булевским или булевым базисом в честь английского математика конца XIX в. Джорджа Буля.

3

Булевая функция

Булевой функцией  f(X1, X2, …, Xn) называется произвольная n – местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

4

СДНФ

Совершенная дизъюнктивная нормальная форма-дизъюнкция элементарных конъюнкций.

5

СКНФ

Совершенная конъюнктивная нормальная форма-конъюнкция  элементарных дизъюнкций.

6

Элементарная конъюнкция

Конъюнкция переменных, их отрицаний, каждое из которых использовано только 1 раз.

7

Элементарная дизъюнкция

Дизъюнкция  переменных, их отрицаний, каждое из которых использовано только 1 раз.

8

Классы функций

Т0 –нулевая функция, принимает нулевое значение при нулевом наборе переменных

Т1-единичная функция, принимает значение единицы при единичном наборе переменных

L-линейная функция, если функция может быть представлена в виде Полинома Жегалкина с переменными в степени не более 1

S-самодвойственная функция, при противоположных наборах переменных принимает противоположные значения

M-монотонная функция, если она меняет свое значение в таблице истинности только 1 раз, при чем этот переход должен быть от 0 к 1

9

Полином Жегалкина

Способ задания логической функции. Для того, чтобы составить ПЖ необходимо:

1.Представить в виде ДНФ;

2.С помощью двойного отрицания и закона де Моргана избавиться от дизъюнкции;

3.Все отрицания заменить по формуле:=x+1;

4.Перемножить полученные скобки;

5.Сократить с учетом: четное количество одинаковых слагаемых превращается в 0, а нечетное- значит оставляем одну переменную

10

Теорема Поста (о полноте)

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f1, …, fm} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T0, T1, L, M, S нашлась хотя бы одна функция fi  из системы, не принадлежащая этому классу.

11

Карта Карно

Позволяет упростить запись таблицы истинности и найти сокращенную запись функции

12

Тождественно-истинная функция

Предикат, если при всех возможных значениях переменных он принимает значение 1

13

Тождественно-ложная функция

Предикат, если при всех возможных значениях переменных он принимает значение 0

№ п/п

Новые понятия

Содержание

1

Алгебра Логики

Совокупность логического множества и логического базиса. Логическое множество состоит из 0 и 1 и означает истину или ложь.

2

Логическая функция

Логической ( булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

3

Логическая переменная

Переменные, которые могут принимать только 2 логических значения «истина» или «ложь»

4

Конъюнкция

(логи́ческое "И",логи́ческое умноже́ние)логическая операция относительно 2х логических переменных, которые принимают значение истины только тогда, когда обе переменные истины

5

Дизъюнкция

(логи́ческое "Или",логи́ческое сложе́ние)Логическая операция относительно 2х переменных, которые принимают ложное значение только тогда, когда обе переменные ложны

6

Импликация

(логи́ческое следование)Логическая операция относительно 2х переменных, которая принимает значение ложно, когда первая переменная истина, а вторая – ложна. Первая переменная – посылка, вторая - заключение

7

Эквивалентность

(логическая равносильность, логическое равенство) Логическая операция относительно 2х переменных, которая принимает значение истины, если переменные равнозначны

8

Инверсия

(логическое отрицание) Логическая операция относительно одной переменной, которая меняет свое значение на противоположное

9

Основные законы логики

·  Основные черты правильного мышления.( мышление, которое соответствует логическим нормам и законам.)

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

·       Закон непротиворечия (противоречия).( логический закон, согласно которому не могут быть одновременно истинными взаимно исключающие друг друга мысли.) Закон противоречия Математическая запись где  — знак конъюнкции,  — знак отрицания.

·       Закон исключенного третьего.( закон традиционной формальной логики, согласно которому из двух формально противоречащих друг другу мыслей одна обязательно должна быть истинной, а вторая ложной.) В математической логике закон исключенного третьего выражается формулой  где  — знак дизъюнкции,  — знак отрицания.

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

10

Равные логические функции

Функции, которые при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения.