Вопросы по матлогике

ВОПРОСЫ 16-18

МЕТОДЫ ДОКАЗАТЕЛЬСТВ

При доказательстве теорем применяется логическая аргументация. Доказательства в информатике — неотъемлемая часть проверки корректности алгоритмов. Необходимость доказательства возника­ет, когда нам нужно установить истинность высказывания вида (Р => Q). Существует несколько стандартных типов доказательств, включающих следующие:

Прямое рассуждение (импликация). Предполагаем, что высказывание Р ис­тинно и показываем справедливость Q. Такой способ доказатель­ства исключает ситуацию, когда Р истинно, a Q — ложно, посколь­ку именно в этом и только в этом случае импликация (Р => Q) принимает ложное значение.

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

Решение. Прежде всего заметим, что любое нечетное число, и в частности х, можно записать в виде х = 2т + 1, где т — целое число. Аналогично, у = 2п + 1 с некоторым целым п.

Значит, произведение

ху = (2т + 1)(2 п + 1) = 4 тп + 2т + 2п + 1 = 2(2 тп + т + п) + 1 тоже является нечетным числом.

Таблица истинности импликации

Обратное рассуждение(контрапозиция). Предполагаем, что высказывание Q ложно и показываем ошибочность Р. То есть, фактически, прямым способом проверяем истинность импликации ((не Q) => (не Р)), что логически эквивалентно истинности ис­ходного утверждения (Р => Q).

Пример 2. Пусть п — натуральное число. Покажите, исполь­зуя обратный способ доказательства, что если п2 нечетно, то и п нечетно.

Решение. Отрицанием высказывания о нечетности числа п2 слу­жит утверждение «п2 четно», а высказывание о четности п явля­ется отрицанием утверждения «число п нечетно». Таким образом, нам нужно показать прямым способом рассуждений, что четность числа п влечет четность его квадрата п2.

Так как п четно, то n = 2т для какого-то целого числа т. Сле­довательно, п2 = 4m2 = 2(2m2) — четное число.

Метод «от противного» (reduction ad absurdus). Предположив, что высказывание Р истинно, a Q ложно, используя аргументированное рассуждение, по­лучаем противоречие. Этот способ опять-таки основан на том, что импликация (Р => Q) принимает ложное значение только тогда, ко­гда Р истинно, a Q ложно.

Пример 3. Доказательство иррациональности числа

Решение.

Допустим противное: рационален, то есть представляется в виде несократимой дроби , где и  — целые числа. Возведём предполагаемое равенство в квадрат:

.

Отсюда следует, что чётно, значит, чётно и ; следовательно, делится на 4, а значит, и тоже чётны. Полученное утверждение противоречит несократимости дроби . Значит, исходное предположение было неверным, и  — иррациональное число.

ВОПРОС 19

Полные системы связок.

Системой связок называется набор базовых функций рассматриваемой алгебры (сигнатура).

Система связок является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только связок входящих в эту систему.

Примеры полных систем связок:

·  Система (отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция) является полной.
·  Система (отрицание, конъюнкция, дизъюнкция) является полной. Именно она и составляет сигнатуру Булевой Алгебры.
·  Система связок (отрицание, импликация)
·  Система штрих Шеффера, И-НЕ является важной для микроэлектроники
·  Система (сумма по модулю 2, конъюнкция) — система Жегалкина
Критерий Поста:
Набор булевых функций является полным тогда и только тогда, когда он не содержится целиком ни в одном из пяти следующих классов:
1. монотонные функции;
2. функции, сохраняющие нуль;
3. функции, сохраняющие единицу;
4. линейные функции;
5. самодвойственные функции.
Если набор содержится в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому набор не является полным.

Система A = {∨, &, } является полной.

Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x ⋅ x. Теорема доказана.

ВОПРОСЫ 20 — 22

ДНФ

Пусть p1,p2,p3…pn — простые высказывания. Назовем выражение x1˄x2˄x3˄…˄xn, в котором хi = рi или хi = ~рi, элементарной конъюнкцией. Выражение, представляющее собой дизъюнкцию элементарных конъюнкций, называется дизъюнктивной нормальной формой, так что если m1,m2,m3…mn есть элементарные конъюнкции, тогда m1˅m2˅m3˅…˅mn есть дизъюнктивная нормальная форма.

КНФ

Пусть p1,p2,p3…pn — простые высказывания. Назовем выражение x1˅x2˅x3˅…˅xn, в котором хi = рi или хi = ~рi, элементарной дизъюнкцией. Выражение, представляющее собой конъюнкцию элементарных дизъюнкций, называется конъюнктивной нормальной формой, так что если m1,m2,m3…mn — элементарные дизъюнкции, то m1˄m2˄m3˄…˄mn есть конъюнктивная нормальная форма.

Полнота ДНФ, КНФ:

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

(конъюнкция, дизъюнкция, отрицание); (конъюнкция, сложение по модулю два, константа один).

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина. Любую булеву функцию можно представить в виде ДНФ или КНФ.

Рассмотрим два способа построения ДНФ и КНФ:

Способ 1. (Метод эквивалентных преобразований). Пусть булева

функция f ( x1 , x 2 , … , x n ) задана формулой. Алгоритм построения ДНФ и

КНФ состоит в следующем:

Шаг 1. Формулу преобразовать так, чтобы в ней были только операции .

Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отрицания стоял лишь над отдельными переменными.

Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону A( B Ú C ) = AB Ú AC при построении ДНФ и по 2-му дистрибутивному закону A ˄ BC = ( A ˄ B )( A ˄ C ) при построении КНФ.

Способ 2. (С использованием таблицы истинности).

Пусть функция f ( x1 , x 2 , … , x n ) задана таблицей истинности.

Для ДНФ:

Шаг 1. Выделить в таблице истинности все наборы переменных, на которых функция принимает единичные значения.

Шаг 2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие без инверсии переменные, принимающие в соответствующем наборе значение 1 и с инверсией —

переменные, принимающие значение 0.

Шаг 3. Соединить элементарные конъюнкции знаком дизъюнкции.

Для КНФ:

Шаг 1. Выделить в таблице истинности все наборы переменных, на которых функция принимает нулевые значения.

Шаг 2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие без инверсии переменные, принимающие в соответствующем наборе значение 0 и с инверсией — переменные, принимающие значение 1.

Шаг 3. Соединить элементарные дизъюнкции знаком конъюнкции.

Полином Жегалкина — полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики. Полином Жегалкина имеет следующий вид:

f(x, y,z) = (y & z) (x & z) x (x & y & z), где

1.  x  y = y  x;

2.  x ( y  z )  =  x y  x z;

3.  x  x = 0; 

4.  x   = 1; 

5.  x  0 = x.

Полнота ДНФ, КНФ и полинома Жегалкина:

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали

Хотя бы одна функция, не сохраняющая 0; Хотя бы одна функция, не сохраняющая 1; Хотя бы одна нелинейная функция; Хотя бы одна немонотонная функция; Хотя бы одна несамодвойственная функция.

Исходя из этого, система функций является полной, так как в ней:

Не сохраняет 0: ; Не сохраняет 1: ; Нелинейна: ; Немонотонна: ;

Рассмотрим два метода построения полинома Жегалкина:

Метод неопределённых коэффициентов

Построить таблицу истинности для данной булевой функции. Записать общий вид полинома Жегалкина для этой функции. Это сумма по модулю два сочетаний переменных длиной от 0 до количества переменных с неопределённым коэффициентом. Элементы в слагаемых соединены конъюнкцией. В таблице напротив каждого набора значений переменных записать сумму по модулю два коэффициентов по следующим правилам:

свободный коэффициент присутствует всегда; остальные коэффициенты есть в сумме тогда, когда все их переменные равны 1 в данном наборе значений.

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

Метод преобразований

Построить СДНФ булевой функции. Заменить дизъюнкцию в полученной СДНФ на сложение по модулю два. Сделать замену: . Раскрыть скобки, пользуясь дистрибутивностью конъюнкции относительно сложения по модулю два: . Сократить лишние сомножители и слагаемые, пользуясь эквивалентностями:

ВОПРОС 23

Карты Карно — это графическое представление операций попарного неполного склеивания и элементарного поглощения.

Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно — определенная плоская развертка n-мерного булева куба.

Строится таблица истинности функции определенным образом. Каждая клетка таблицы соответствует вполне определенной вершине булева куба. Нулевые значения не записываются. Если высказыванию соответствует карта Карно с двумя соседствующими в строке или в столбце х, тогда выражение можно упростить, сведя две элементарные конъюнкции к одной, содержащей на одну компоненту.

Перечислим четыре последовательных шага при использовании карты Карно:

1. Для каждой элементарной конъюнкции обозначьте на карте соответствую —

щий прямоугольник.

2. Покройте знаки, используя, по возможности, несколько прямоугольных бло —

ков.

3. Используйте блоки, максимальные по величине, не меняя числа блоков.

4. Оцените блоки с соответствующими высказываниями, которые описывают

их, и объедините эти высказывания символом V.

Карта Карно для 2х переменных

Карта Карно для 2х переменных

Количество клеток 2^n (2 в степени n), где n количество входных переменных т. е. 2^2 = 4.

  Координаты клеток карты Карно расставить таким образом, чтобы координаты соседних клеток отличались на одну переменную.
На основании ДНФ в клетки карты расставляются единицы, каждое слагаемое ДНФ это координата клетки. Единицы находящиеся в соседних клетках объясняются в группы, количество единиц в каждой группе должно быть кратно 2^n, n-любое натуральное число.
  Каждая группа единиц дает слагаемое равное произведению тех иксов в поле которых эта группа находится целиком.
Получаем

Карта Карно для 3х переменных

Карта строится таким же образом как и для 2х переменных,  поэтому надо сначала прочитать для 2х переменных

Записываем координаты наших групп. Получаем:

Карта Карно для 4х переменных

Строятся так по таким же правилам как и для 2х и 3х переменных

По данной таблице составляем ДНФ

Далее все по аналогии как в картах Карно для 2х и 3х переменных.

Записываем координаты получившихся групп, получаем СДНФ

Примеры объединения групп 

ВОПРОСЫ 24 — 25

ПРЕДИКАТЫ И КВАНТОРЫ

Понятие предиката

Предикатом называется утверждение, содержащее переменные, принимающее значение истины или лжи в зависимости от значений переменных. Например, выражение «х — целое число, удовлетворя­ющее соотношению х = х2» является предикатом, поскольку оно истинно при х = 0 или х = 1 и ложно в любом другом случае.

Действия с предикатами

Логические операции можно применять и к предикатам. В общем случае истинность составного предиката в конечном счете зависит от значений входящих в него переменных. Однако существуют кванторы, применение которых к предикатам превращает последние в ложные или истинные высказывания.

Примеры

Пример 1 Какие из следующих высказываний истинны, а какие ложны?

(а) Сумма внутренних углов любого треугольника равна 180°. (Истинно.)

(б) У всех кошек есть хвост. (Ложно. У бесхвостой1 кошки хвоста нет.)

(в) Найдется целое число х, удовлетворяющее соотношению х2 = 2. (Ложно.)

(г) Существует простое четное число. (Истинно. Число 2 является и простым, и четным.)

Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:

Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»). Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).

В математической логике приписывание квантора к формуле называется связыванием или квантификацией.

В примере 1 мы имеем дело с набором объектов и утвержде­ниями о том, что некоторое свойство имеет место для всех рассма­триваемых объектов, или что найдется (существует) по крайней мере один объект, обладающий данным свойством. Выражения «для всех» и «найдется» («существует») называют­ся кванторами и обозначаются, соответственно, и . Включая в предикат кванторы, мы превращаем его в высказывание.

Построение утверждения:

Пример 2 Предположим, что х и у — вещественные числа, а Р(х, у) обозначает предикат х + у = 0.

(а) Высказывание xу: Р(х, у) говорит о том, что для любого вещественного числа х найдется такое вещественное число у, что х + у = 0. Оно, очевидно, верно, поскольку какое бы число х мы ни взяли, число у = — х обращает равенство х + у = 0 в верное тождество.

(б) Высказывание у : х Р(х, у) читается следующим образом: существует такое вещественное число у, что для любого веще­ственного числа х выполнено равенство х + у = 0. Это, конеч­но, не так: не существует вещественного числа у, обладающего указанным свойством. Следовательно, высказывание ложно.

Построение отрицания

Правило отрицания кванторов  применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:

Пример 3

Пусть Р(х) — предикат: «х — вещественное число и х2 + 1 = 0». Отрицание данного высказывания записывается в следую­щем виде: не х : Р(х). Это, естественно, истинное высказывание, которое означает, что не существует вещественного числа х, удо­влетворяющего условию х2 + 1 = 0. Иными словами, каково бы ни было вещественное х, х2 + 1 ≠ 0. В символьной форме это можно записать как x не Р(х).

ВОПРОСЫ 26 – 27

Принцип математической индукции

Пусть Р(n) есть такое утверждение, что

а) Р(1) истинно, и

б) для каждого k, если Р(k) истинно, то Р(k + 1) истинно.

Тогда Р(n) истинно для любого целого положительного числа n. В символической записи принцип математической индукции имеет вид:

(Р(1) ˄ ((k) Р(k) → Р(k + 1)) → (n) P(n).

Примеры:

Применяя метод математической индукции, доказать, что для любого натурального n справедливы следующие равенства:

а)
 б) ; .