Построение таблиц истинности и логических функций

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a , b ).

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

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквивалентность.

Для изменения указанного порядка выполнения операций используются скобки.

Алгоритм построения таблиц истинности для сложных выражений :

количество строк = 2 n + строка для заголовка ,

n - количество простых высказываний.

количество столбцов = количество переменных + количество логических операций ;

· определить количество переменных (простых выражений);

· определить количество логических операций и последовательность их выполнения.

3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.

Пример: Составить таблицу истинности логического выражения:

D = А & ( B V C )

Решение:

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n =3 и количество строк = 23 +1 = 9.

2. Определить количество столбцов:

простые выражения (переменные): А, В, С ;

промежуточные результаты (логические операции):

А - инверсия (обозначим через E );

B V C - операция дизъюнкции (обозначим через F );

а также искомое окончательное значение арифметического выражения:

D = А & ( B V C ) . т. е. D = E & F - это операция конъюнкции.

Заполнить столбцы с учетом таблиц истинности логических операций.

font-size:12.0pt">Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z (X ,Y ):

font-size:12.0pt">1 .

Так как строки две, получаем дизъюнкцию двух элементов: () V () .

Каждый логический элемент в этой дизъюнкции запишем в виде конъюнкции аргументов функции X и Y : ( X & Y ) V ( X & Y ).

Решение логических выражений принято записывать в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.

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

1. действия в скобках,
2. инверсия (отрицание ),
3. & (конъюнкция ),
4. v (дизъюнкция ),
5. => (импликация ),
6. <=> (эквивалентность ).

Алгоритм составления таблицы истинности :

1. Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных + строка заголовков столбцов).

2. Выяснить количество столбцов (вычисляется как количество переменных + количество логических операций).

3. Установить последовательность выполнения логических операций.

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

5. Заполнить таблицу истинности по столбцам.

6. Записать ответ.

Упражнение 8

Постройте таблицы истинности для следующих логических выражений:

1. F =(Av B )&(¬ A& ¬ B).

2. F = X&¬ Yv Z.

Проверьте себя (эталон ответов)

Обратите внимание!

Тавтология - тождественно истинная формула истина " ("1

Противоречие - тождественно ложная формула , или формула принимающая значение "ложь " ("0 ") при любых входящих в нее значениях переменных.

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

Информатика: аппаратные средства персонального компьютера Яшин Владимир Николаевич

4.3. Логические функции и таблицы истинности

Соотношения между логическими переменными и логическими функциями в алгебре логики можно отобразить также с помощью соответствующих таблиц, которые носят название таблиц истинности. Таблицы истинности находят широкое применение, поскольку наглядно показывают, какие значения принимает логическая функция при всех сочетаниях значений ее логических переменных. Таблица истинности состоит из двух частей. Первая (левая) часть относится к логическим переменным и содержит полный перечень возможных комбинаций логических переменных А, В, С… и т. д. Вторая (правая) часть этой таблицы определяет выходные состояния как логическую функцию от комбинаций входных величин.

Например, для логической функции F = A v B v C (дизъюнкции) трех логических переменных А, В, и С таблица истинности будет иметь вид, показанный на рис. 4.1. Для записи значений логических переменных и логической функции данная таблица истинности содержит 8 строк и 4 столбца, т. е. число строк для записи значений аргументов и функции любой таблицы истинности будет равно 2 n , где п – число аргументов логической функции, а число столбцов равно п + 1.

Рис. 4.1. Таблица истинности для логической функции F = A v В v С

Таблицу истинности можно составить для любой логической функции, например, на рис. 4.2 приведена таблица истинности логической функции F = A ? B ? C (эквиваленции).

Логические функции имеют соответствующие названия. Для двух двоичных переменных существует шестнадцать логических функций, названия которых приведены ниже. На рис. 4.3 представлена таблица, в которой приведены логические функции F 1 , F 2 , F 3 , … , F 16 двух логических переменных A и В.

Функция F 1 = 0 и называется функцией константы нуля, или генератора нуля.

Рис. 4.2. Таблица истинности для логической функции F = A ? B ? C

Рис. 4.3. Логические функции F 1 , F 2 , F 3 ,… F 16 двух аргументов А и В

Функция F 2 = A & B называется функцией конъюнкции.

А.

Функция F 4 = А А.

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

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

называется функцией исключающее «ИЛИ».

Функция F 8 = A v В называется функцией дизъюнкции.

называется функцией Пирса.

называется функцией эквиваленции.

В.

Функция F 12 = B ? A B ? A.

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

Функция F 14 = A ? B называется функцией импликации A ? B .

называется функцией Шеффера.

Функция F 16 = 1 называется функцией генератора 1.

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

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

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

Рис. 4.4. Диалоговое окно «Мастер функций – шаг 1 из 2»

Как видно из рис. 4.4, в состав логических функций программы MS Excel входит функционально полный набор логических функций, состоящий из следующих логических функций: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание). Таким образом, с помощью функционально полного набора логических функций программы MS Excel можно реализовать другие функции. Логическая функция ЕСЛИ (импликация), также входящая в логические функции MS Excel, выполняет логическую проверку и в зависимости от результата проверки выполняет одно из двух возможных действий. В данной программе она имеет следующий формат: = ЕСЛИ (арг1;арг2;арг3), где арг1 – логическое условие; арг2 – возвращаемое значение при условии, что значение аргумента арг1 выполняется (ИСТИНА); арг3 – возвращаемое значение при условии, что значение аргумента арг1 не выполняется (ЛОЖЬ). Например, если в произвольную ячейку листа программы MS Excel ввести выражение « = ЕСЛИ (А1 = 5; „пять“; „не пять“)», то при вводе числа 5 в ячейку А1 и нажатии клавиши «Enter» в ячейке А1 автоматически будет записано слово «пять», при вводе любого другого числа в ячейку А1 в ней запишется слово «не пять». Как уже отмечалось, с помощью логических функций программы MS Excel можно представить другие логические функции и соответствующие им таблицы истинности.

Реализуем с помощью логических функций ЕСЛИ и И модифицированную таблицу истинности логической функции F = А & В (конъюнкции), состоящую из двух строк и трех столбцов, которая позволяет при изменении значений (0 или 1) логических переменных А и В автоматически устанавливать, например, в ячейке Е6 значение функции F = А & В, соответствующее значениям этих логических переменных. Для этого в ячейку Е6 введем следующее выражение: «=ЕСЛИ(И(С6;D6);1;0)», тогда при вводе в ячейки С6 и D6 значений 0 или 1 в ячейке Е6 будет выполняться логическая функция F = А & В. Результат этих действий представлен на рис. 4.5.

Рис. 4.5. Реализация модифицированной таблицы истинности логической функции F = A & В

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

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

Логические функции Логические функции могут найти применение при математических, инженерных вычислениях или при сравнительном анализе данных. Мы рассмотрим одну логическую функцию на примере функции ЕСЛИ.С помощью функции ЕСЛИ вы можете создать логическое выражение и