ТОР 5 статей:

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

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:

Пример.Построить таблицу истинности формулы .

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒

Порядок действий:

1. Определим порядок действий в формуле: .

2. Пользуясь определениями логических операций , заполним таблицу истинности.

Булевы функции

Булевы функции находят применение в проектировании и упрощении логических схем. Такие схемы встречаются в электронных устройствах, используемых в компьютерах, калькуляторах, телефонных системах и ряде других устройств.

Булевы функции часто задаются таблично. Эти таблицы напоминают таблицы истинности логических операций, поэтому сами булевы функции часто называют булевыми операциями, а соответствующие им таблицы таблицами истинности.

	Значения переменной	Булевы функции одной переменной
х			Название функции	Формула, реализующая функцию функции
y₀			Тождественный ноль	0
y₁			Тождественная переменной	х
y₂			Отрицание переменной
y₃			Тождественная единица переменной	1

	Значения переменной	Булевы функции двух переменных
х₁			Название функции	Формула, реализующая функцию
х₂
y₀			Тождественный ноль	0
y₁			Конъюнкция, И
y₂			Отрицание импликации
y₃			Тождественная первой переменной
y₄			Отрицание импликации
y₅			Тождественная второй переменной
y₆			Сумма по модулю два, строгая дизъюнкция
y₇			Дизъюнкция, ИЛИ
y₈			Стрелка Пирса, ИЛИ-НЕ
y₉			Эквиваленция
y₁₀			Инверсия второй переменной
y₁₁			Импликация
y₁₂			Инверсия первой переменной
y₁₃			Импликация
y₁₄			Штрих Шеффера, И-НЕ
y₁₅			Тождественная единица	1

Логические законы

Название закона	Запись закона в алгебре высказываний	Запись закона в алгебре Буля	Смысл
Коммутативный	А В = В А А В = В А		Коммутативность означает, что можно менять местами члены конъюнкции (дизъюнкции).
Ассоциативный			Ассоциативность означает, что можно не ставить скобки при нескольких последовательных применениях конъюнкции (дизъюнкции) или наоборот ставить их, так как удобно.
Дистрибутивный	А (В С) = (А В) (А С) А (В С) = (А В) (А С)		Дистрибутивность означает, что можно раскрывать скобки при применениях конъюнкции к дизъюнкции и наоборот.
Идемпотентность	А А = А А А = А		Определяет результат конъюнкции (дизъюнкции) для двух одинаковых членов.
Закон исключенного третьего			Для каждого высказывания истинно либо оно, либо его отрицание.
Закон противоречия			Одно и то же высказывание не может быть одновременно истинным и ложным.
Закон двойного отрицания			Двойное отрицание высказывания равносильно этому высказыванию.
Законы действий с константами			Действия с 0 и 1.
Закон Де Моргана			Инверсию над конъюнкцией (дизъюнкцией) переменных можно «протащить» на каждую переменную, но знак () при этом меняем на ().
Закон поглощения	А (А В) = А А (А В) = А		Переменная у (В) «поглощается», остается только переменная х (А)
Снятие импликации, эквиваленции и строгой дизъюнкции	, , .	, , .	Закон позволяет перейти от операций к базовым операциям .

СДНФ и СКНФ

(•) + (•)

Алгоритм составления СДНФ:

1. Составляем таблицу истинности формулы.

2. Выбираем наборы переменных, на которых функция равна 1.

3. Каждому выбранному набору ставим в соответствие полную совершенную элементарную конъюнкцию:

- если значение переменной в этом наборе равно 0, то эта переменная берется с отрицанием.

- если значение переменной в этом наборе равно 1, то эта переменная берется без отрицания.

4. Соединяем полученные элементарные конъюнкции операцией дизъюнкции (+), получаем СДНФ.

Алгоритм составления СКНФ:

1. Составляем таблицу истинности формулы.

2. Выбираем наборы переменных, на которых функция равна 0.

3. Каждому выбранному набору ставим в соответствие полную совершенную элементарную дизъюнкцию:

- если значение переменной в этом наборе равно 1, то эта переменная берется с отрицанием.

- если значение переменной в этом наборе равно 0, то эта переменная берется без отрицания.

4. Соединяем полученные элементарные дизъюнкции операцией конъюнкции (•), получаем СКНФ.

Карты Карно. МДНФ

Алгоритм минимизацииСДНФ формул с помощью карт Карно: 1. Разбиваем переменные на две группы. Например: F (x₁,x₂): x₁ и x₂ F (x₁,x₂,x₃): x₁x₂ и x₃ (или x₁ и x₂x₃) F (x₁,x₂,x₃,x₄): x₁x₂ и x₃x₄ 2.Составляем таблицу, в которой по горизонтали расположены в циклическом порядке все возможные наборы переменных и их отрицаний из первой группы, по вертикали наборы переменных и их отрицаний из второй группы. 3. В ячейках таблицы ставим 1, если соответствующая элементарная конъюнкция входит в СДНФ. 4. Объединяем соседние 1 контурами по правилам. 5. Внутри каждого контура исключаем члены, дополняющие друг друга до 1 (т.е.

). 6. Объединяем оставшиеся члены операцией дизъюнкции, получаем МДНФ (минимальную дизъюнктивную нормальную форму).

Пример. Минимизируем функции трех переменных с помощью карт Карно.

1. Разобьем переменные на две группы x₁ и x₂x₃.

2. Заполняем карту Карно.

3. Объединяем соседние единицы контурами, считаем соседними ячейки расположенные на противоположных краях карты.

1 1

1

4. Внутри каждого контура исключаем члены, дополняющие друг друга до 1 (т.е. ).

5. Объединим оставшиеся члены дизъюнкцией.

6. Запишем полученное выражение .

Предикаты и кванторы

Виды предикатов

- одноместный предикат;

- двух местный предикат;

- n – местный предикат.

Пример.

Одноместный предикат .

Двух местный предикат : Студент x учится в группе y.

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных