Алгебра логики высказываний Основные понятия
Скачать 428.51 Kb.
|
Функции алгебры логикиЗначение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в нее элементарных высказываний. Например, (x y) z является функцией f(x, y, z). Естественно, значения этой функции и входящих в нее элементов могут принимать значения истина или ложь. Тождественно истинные или тождественно ложные функции представляют собой константы. Каждую функцию алгебры логики можно записать в виде формулы или представить таблицей истинности. Как уже было отмечено выше, таблица истинности для n переменных содержит 2n строк. Следовательно, каждая функция алгебры логики принимает 2n значений, состоящих из 0 или 1. Общее же число наборов значений, состоящих из 0 и 1, длины 2n равно 22n. В частности, число различных функций от одной переменной равно четырем.
Из этой таблицы следует, что две функции являются константами f1(x) = 1 и – f2(x) = x, а остальные f3(x) = x и f4(x) = 0. Представление произвольной логической функции в виде формулы алгебры логикиПусть с помощью таблицы истинности задана произвольная функция алгебры логики n переменных F(x1, x2, …, xn). Рассмотрим формулу: F(1, 1, …, 1) x1 x2 … xn F(1, 1, …, 1, 0) x1 x2 … xn-1 xn (1) F(1, 1, …, 0, 1) x1 x2 … xn-1 xn F(0, 0, …, 0) x1 x2 … xn которая составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой первый член является значением функции F при некоторых определенных значениях ее переменных, остальные же члены конъюнкции представляют собой сами переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют значение 0. Ясно, что формула (1) полностью определяет функцию F. Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений переменных xi. Например, если x1 принимает значение 0, а остальные переменные принимают значение 1, то функция F принимает значение F(0, 1, 1, …, 1). При этом логическое слагаемое F(0, 1, …, 1) x1 x2 … xn = F(0, 1, …, 1) 0 1 … 1, входящее в формулу (1), принимает также значение F(0, l,..., l), а все остальные логические слагаемые формулы (1) имеют значение 0. Действительно, в них знаки отрицания перед переменными распределяются иначе, чем в рассмотренном слагаемом. Таким образом, при подстановке вместо переменных тех же значений в конъюнкцию войдет символ 0 без знака отрицания, а символ 1 под знаком отрицания. В таком случае один из членов конъюнкции будет иметь значение 0, и поэтому вся конъюнкция также будет иметь значение 0. В связи с этим на основании закона x 0 = x значением формулы (1) является F(0, l,..., l). Ясно, что вид формулы (1) может быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно, вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнкции (то есть определенное значение функции F) имеет значение 1, то, пользуясь законом 1 х = x, этот член конъюнкции можно не выписывать. Таким образом, в результате получается формула (1), которая содержит только элементарные переменные высказывания и обладает следующими свойствами:
Перечисленные свойства будем называть свойствами совершенства или, коротко, свойствами. Из приведенных рассуждений видно, что каждой не тождественно ложной функции соответствует единственная формула указанного вида. Если функция F(x1, x2, …, xn) задана таблицей истинности, то соответствующая ей формула алгебры логики может быть получена просто. Действительно, для каждого набора значений переменных, на котором функция F(x1, x2, …, xn) принимает значение 1, записывается конъюнкция элементарных переменных высказываний, взяв за член конъюнкции хk, если значение xk на указанном наборе значений переменных функции F есть 1 и х, если значение xk есть 0. Дизъюнкция всех записанных конъюнкций и будет искомой формулой. Пусть, например, функция F(x1, x2, x3) имеет следующую таблицу истинности:
Для наборов значений переменных (1, 1, 0), (1,0,1), (0,1,0), (0, 0, 0), на которых функция принимает значение 1, запишем конъюнкции x1 x2 x3, x1 x2 x3, x1 x2 x3, x1 x2 x3. а искомая формула, обладающая свойствами совершенства, будет иметь вид: x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3. |
Похожие:
 | 1. «Совершенные дизъюнктивные нормальные формы (сднф) и совершенные... Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим... | | 2. Основы логики и логические основы компьютера Основы логики. Основные... Информационные процессы в живой природе, обществе и технике: получение, передача, преобразование, хранение и использование информации.... |
 | «Основные логические элементы» Данный урок является частью темы «Алгебра логики». Необходимость изучения данной темы обусловлена значением переключательных схем... | | Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика |
| Программа по дисциплине «прикладные протоколы интернет и www» Глобальные вычислительные сети: os unix – основные понятия, Internet – структура и основные понятия, аппаратное обеспечение, программное... | | Урок №47. Формы мышления. Алгебра высказываний. Цели урока Правомерно ли считать, что религия, искусство, наука – духовные истоки философии? Обоснуйте свой ответ |
| Конспект урока Тема: Алгебра логики. Решение задач с элементами алгебры логики Планируемый результат: учащиеся решат задачу на движение, используя ос решения текстовой задачи, продемонстрируют уровень усвоения... | | Реферат по информатике и икт на тему: «Логика» Что такое алгебра логики стр. 4 |
| Тема: Основные понятия математической логики Автор, к своему стыду, до сих пор иногда путает и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком... | | Программа предназначена для преподавателей, ведущих данную дисциплину,... Цель урока: закрепить основные понятия, рассматриваемые в законах механики Ньютона |
| «Волшебный компьютер» (35 часов) Свойства информации. Язык представления информации. Кодирование информации. Основные понятия логики. Понятие графов. Устройство персонального... | | Урок 1 Тема урока : Логика как наука. Основные понятия математической логики Учебный курс (рабочая программа) «Логика научного исследования» для аспирантов очной и заочной форм обучения специальностей 09. 00.... |
| Тема : Основные понятия математической логики А представляет собой двоичную запись числа 226, столбец значений аргумента в – числа 154, столбец значений аргумента с – числа 75.... | | Урок лекция План проведения урока Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной... |
| Программа по формированию навыков безопасного поведения на дорогах... Цели Помочь учащимся осознать понятия: грех, гордость, смирение на примере отрывка из Священной истории «Мытарь и Фарисей», высказываний... | | Программа по формированию навыков безопасного поведения на дорогах... Мотивы, которые побудили выбрать тему «Алгебра логики и логические элементы персонального компьютера» для создания данного комплекса... |
