Содержание
-
Основы математической логики
-
Булевы функции от одного, двух аргументов и от n аргументов
-
Булевы функции. Канонический многочлен Жегалкина
-
Булевы функции от одного аргумента
Булевой функцией от одного аргумента называется функция f, заданная на множестве из двух элементов и принимающая значения в том же двухэлементном множестве. f :{0,1} → {0,1}
-
f0 (x) = 0 (функция, тождественно равная 0) f1 (x) = x (тождественная функция) f2 (x) = x’ (функция отрицания) f3 (x) = 1 (функция, тождественно равная 1)
-
Булевы функции от двух аргументов
Булевой функцией от двух аргументов называется функция g, заданная на множестве {0,1} ×{0,1} и принимающая значение в двухэлементном множестве {0,1}
-
Сумма по модулю два
Сумма по модулю два (строгая дизъюнкция) двух переменных x1 иx2 называется булева функция x1x2 которая равна 1 тогда и только тогда, когда равна 1 только одна переменная. x1 x2
-
Законы, применимые для суммы по модулю два: Переместительный x1x2=x2x1 Сочетательный (x1x2) x3 = x1(x2 x3) Распределительный конъюнкции x1(x2 x3) = x1x2 x1x3
-
Операции с константами: x x = 0 x 0 = х x x = 1 x 1 = х Разложение в СДНФ: x1 x2= x1x2 x1x2 x1 x2= x1 x2= x1 x2
-
Связь между дизъюнкцией с суммой по модулю два: x1 x2 = x1 x2 x1x2 Конъюнкция: x1 x2= x1 x2 (x1 x2)
-
Логический элемент М2 – сумма по модулю два
На практике в электронике реализовать сложно. Элемент М2 реализуют из простых устойчивых элементов: И, ИЛИ, НЕ.
-
Применение
Для проверки результатов сложения в двоичном сумматоре для системы контроля и исправления ошибок: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = (1)0
-
Почему «сумма по модулю два»?
Остаток от деления целых чисел М на N: M mod N Рассмотрим множество Z2 ={0,1} и произведем операцию: (a + b) mod 2 (0 + 0) mod 2 = 0 (0 + 1) mod 2 = 1 (1 + 0) mod 2 = 1 (1 + 1) mod 2 = 0
-
Канонический полином Жегалкина
f(x1x2…xn) = f0 f1x1 f2x2… fnxn f12x1x2… f12…nx1x2…xn, f1…fn B = {0,1}
-
Пример: F(x1x2x3) = =x1x2x3 x1x2x3 x1x2x3 x1x2x3 = =(1x1)x2(1x3) x1(1 x2)(1 x3) x1(1 x2)x3 x1x2x3 = =(x2x1x2)(1x3) (x1 x1x2)(1 x3) (x1 x1x2)x3 x1x2x3 = =x2x1x2x2x3 x1x2x3x1x1x2x1x3x1x2x3x1x3x1x2x3x1x2x3= = x2x2x3 x1 x1x2x3 x1x2x3 Любую логическую функцию можно единственным образом представить в виде полинома Жегалкина
-
2-й способ: Многочлен с неопределенным коэффициентом xy= a bx cy dxy При х=0, у=0, то 0 =а При х=0, у=1, то 0=0 с, с=0 При х=1, у=0, то 1 = b 0, b=1 При х=1, y=1, то 0 = 1 d, d=1 хy = x xy
-
Функционально замкнутые классы
Класс функций называется функционально замкнутым, если любая комбинация функций этого класса принадлежит этому же классу.
-
Класс функций, сохраняющих 0 (К0)
-
Важнейшие замкнутые классы. Теорема Поста
-
-
Приложение функций алгебры логики к анализу и синтезу релейно контактных схем
-
-
Логика предикатов
-
Основные понятия, связанные с предикатами
-
Предикаты и высказывательные формы. Равносильность и следование предикатов
-
n- местным предикатом называется предложение, содержащее n предметных переменных х1, х2, … ,хn. Переменные выбираются из множества значений М1, М2, … Мn. При этом предикат превращается в высказывание. P(x1, x2, …, xn) – функция высказывания Примеры: Река х впадает в озеро Байкал. – одноместный предикат, определенный на множестве всех рек. Пусть х = Баргузин, тогда: «Река Баргузин впадает в озеро Байкал» - высказывание истинное Пусть х = Днепр, тогда: «Река Днепр впадает в озеро Байкал» - высказывание ложное
-
Пример
x2+y2 ≤9 Сколько переменных? На каком множестве заданы? При какой паре чисел принимает истинное значение? При какой паре чисел принимает ложное значение? 2 R, R 2, 2 2, 3
-
Классификация предикатов
Предикат называется тождественно истинным, если при любой подстановке в предложение из множества значений он становится истинным высказыванием. P(x1, x2, …, xn) = 1 Пример: sin2x + cos2x = 1
-
Предикат называется тождественно ложным, если при любой подстановке в предложение из множества значений он становится ложным высказыванием. P(x1, x2, …, xn) = 0 Пример:x2 + y2
-
Предикат называется выполнимым (опровержимым), если существует хотя бы один набор конкретных предметов, при подстановке которых он становится истинным (ложным) высказыванием.
-
Примеры: «Город х расположен на берегу реки Волги» «Рыба х живет в высокогорьях» «Рыба х живет в пресном водоеме» «Современный компьютер х обладает операционной системой» «Компьютерная сеть х соединяет у компьютеров»
-
Множество истинности предикатов
Множество истинности предиката – это множество тех значений, при которых предикат превращается в истинное высказывание. Р+ = {(a1, …, an)} : (P(a1, …, an) = 1} Пример: х2 + у2 = 9 Сколько местный это предикат? На каком множестве он простроен? Множество пар действительных чисел, которые являются координатами точек плоскости, образующими окружность радиусом 9
-
Равносильность и следование предикатов
Два n-местных предиката заданных над одним и тем же множеством называются равносильными, если при подстановке одного и того же набора значений превращают оба предиката в истинные высказывания.
-
Переход от предиката Р1 к равносильному ему предикату Р2 называется равносильным преобразованием 4х – 2 = -3х – 9 4х + 3х = 2 – 9 Х = -1 Ответ: {-1} – множество истинности для данного уравнения
-
Следствия предикатов
Предикат Q называется следствием предиката P, если он превращается в истинное высказывание на множестве значений, включенных в множество истинных значений предиката Р. P+ Q+
-
Пример: Q (х1, …, хn) – предикат «множество компьютеров аудитории 22б » Р (х1, …, хn) – предикат «компьютеры колледжа 50»
-
Логические операции над предикатами
-
Отрицание предиката
Отрицанием n-местного предиката Р, определенного на множествах М, называется новый n-местный предикат, определенный на тех же множествах . Обозначение P(x1, … xn) Читается «Неверно, что P(x1, … xn)» Пример: Р(хR) = х 3 Р(хR) = (х 3) = х> 3
-
Конъюнкция двух предикатов
Конъюнкцией n-местного предиката Р, определенного на множествах М и k-местного предиката Q, определенного на множествах L , называется новый (n+k)-местный предикат, определенный на этих множествах . Обозначение P(x1, … xn) Q(y1, … yn) Чтение:«P(x1, … xn) иQ(y1, … yn)» Пример: Р(хR) = х> -3 Q(хR) = х -3 х
-
Дизъюнкция двух предикатов
Дизъюнкцией n-местного предиката Р, определенного на множествах М и k-местного предиката Q, определенного на множествах L , называется новый (n+k)-местный предикат, определенный на этих множествах . Обозначение P(x1, … xn) Q(y1, … yn) Чтение:«P(x1, … xn) илиQ(y1, … yn)» Пример: Р(хR) = х> -3 Q(хR) = х -3 х
-
Примеры
«Х – четное число» «У – простое число» Определены на N
-
-
Кванторные операции над предикатами
-
Кванторы. Отрицание предложений с кванторами
-
Квантор общности
Операция над одноместным предикатом, означающая: x(P(x)) – для всех х имеет место Р(х)
-
Квантор существования
Операция над одноместным предикатом, означающая: x(P(x)) – для всех х имеет место Р(х)
-
Квантор можно применять и к n-местному предикату, в результате получится n-1) – местный предикат. Переменную, к которой относится квантор, называют связанной, остальные переменные – свободные.
-
Какие переменные связанные и какие свободные?
-
1.А(x) = "x – наука"; B(x) = "x гуманитарная". Записать словами: C =x(A(x) B(x)); D =x((A(x)&B(x))). 2. А(x) = "x – рыба"; B(x) = "x дышит жабрами". Записать словами: C =x(A(x) B(x)); D = x(A(x)&B(x)).
-
Он ничего не знает. Некоторые абитуриенты поступили в институт. Студент ответил на некоторые вопросы. Автобус останавливается на всех остановках.
-
1. определить, какие переменные свободные, а какие связанные. 2. Даны предикаты: А(x) и B(x). Записать словами предложенные формулы С и D.
-
Численные кванторы
-
-
Применение логики предикатов к логико-математической практике
-
Запись на языке логики предикатов различных предложений. Строение математических теорем
-
Тождественные преобразования предикатов
-
Х - люди F(x) = «блондины»; G(x) = «ездят на машинах» x(F(x)&G(x)) = x(F(x)& x(G(x) «Для всех людей верно, что они блондины и ездят на машинах» «Все люди блондины и все люди ездят на машинах» x(F(x)G(x) = x(F(x) x (G(x) «Для всех людей верно, что они блондины или ездят на машинах» «Все люди блондины или все люди ездят на машинах» x(F(x)&G(x)) «Неверно для всех людей, что они блондины и ездят на машинах» ( x(F(x)& xG(x)) = x(F(x) xG(x) «Неверно, что все люди блондины и все люди ездят на машинах» «Неверно, что все люди блондины или неверно, что все люди ездят на машинах»
-
x(F(x)G(x)) = x(F(x)) x (G(x)) «Есть люди, которые являются блондинами или ездят на машинах» «Есть люди – блондины или есть люди, ездящие на машинах» x(F(x)&G(x) = x(F(x)& x (G(x)) «Есть люди, которые являются блондинами и ездят на машинах» «Есть люди – блондины и есть люди, ездящие на машинах» x(F(x)G(x)) = ( x(F(x)) x (G(x)) = = x(F(x)) & x(G(x)) «Неверно, что есть люди, которые являются блондинами или ездят на машинах» «Неверно, что есть люди – блондины или есть люди, ездящие на машинах» «Неверно, что есть люди – блондины и есть люди, ездящие на машинах»
-
Перенос квантора через отрицание
x(F(x)) = x (F(x)) «Неверно, что все люди – блондины» «Есть люди –не блондины» ( x(F(x)) = x (F(x)) «Неверно, что некоторые люди – блондины» «Для всех людей неверно, что они – блондины»
-
Вынос квантора за скобки
x(F(x)&G) = x(F(x)) & G «Для некоторых людей верно, что они блондины и машины красного цвета» «Некоторые люди – блондины и машины красного цвета» x(F(x) G) = x(F(x)) G «Для некоторых людей верно, что они блондины или машины красного цвета» «Некоторые люди – блондины или машины красного цвета» x(F(x)&G) = x(F(x)) & G «Для всех людей верно, что они блондины и машины красного цвета» «Все люди – блондины и машины красного цвета» x(F(x) G) = x(F(x)) G «Для всехлюдей верно, что они блондины или машины красного цвета» «Все люди – блондины или машины красного цвета»
-
Принцип математической индукции в предикатной форме
-
Элементы теории алгоритмов
-
Вычислимые функции и алгоритмы
-
Теории алгоритмов
-
-
Свойства алгоритмов
-
-
Простейшие функции
-
-
Рекурсивные функции
-
-
Нормальный алгоритм Маркова. Машина Тьюринга
-
Основные определения. Алгоритм Маркова
-
-
Алгоритм Тьюринга
-
-
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.