Как найти все существенные переменные

Автор	Сообщение
	Заголовок сообщения: Найти существенные и фиктивные переменные двумя способами Добавлено: 29 окт 2014, 13:51
Начинающий Зарегистрирован: 29 окт 2014, 13:42 Сообщений: 5 Cпасибо сказано: 0 Спасибо получено: 0 раз в 0 сообщении Очков репутации: 1	Найти существенные и фиктивные переменные двумя способами функции f(x,y,z)= (10001001)
Вернуться к началу

waise73	Заголовок сообщения: Re: Найти существенные и фиктивные переменные двумя способами Добавлено: 29 окт 2014, 17:01
	x y z f 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
Вернуться к началу

mad_math	Заголовок сообщения: Re: Найти существенные и фиктивные переменные двумя способами Добавлено: 29 окт 2014, 20:13
	А теперь проверяем по таблице, имеются ли такие наборы переменных [math]x,, y,, z,[/math] в которых значения только одной переменной различны, а значения самой функции на этих наборах совпадают. Например, для переменной [math]x[/math]: [math]f(000)=f(100)=1,, f(001)=f(101)=0,, f(010)=f(110)=0[/math], но [math]f(011)ne f(111),[/math] следовательно, переменная [math]x[/math] не является фиктивной.
Вернуться к началу

waise73	Заголовок сообщения: Re: Найти существенные и фиктивные переменные двумя способами Добавлено: 29 окт 2014, 22:52
	Я не совсем понял,как это все делается, можно ли как-то по подробнее или для других переменных тоже показать?
Вернуться к началу

Существенные и фиктивные переменные

В алгебре логики логические операции
часто описываются при помощи так
называемых таблиц истинности.

• Определение Таблица истинности— таблица, устанавливающая соответствие
  между возможными значениями набора
  переменных и значениями функции.

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

• Определение Две функции равны,
  если совпадают их таблицы истинности
  (на объединенном наборе переменных).

Функции одной переменной

Функций от одной переменной четыре: это
константа 0, константа 1,тождественная
функция, т.е. функция, значение которой
совпадает с аргументом и так называемая
функция «отрицание». Отрицание
будем обозначать символом¬как
унарную операцию. Приведём таблицы этих
четырёх функций

Перенумеруем функции (их 4) и
естественным образом и расположим в
виде таблицы:

x	f0	f1	f2	f3
0	0	0	1	1
1	0	1	0	1

Видно, что f₀
(х)
= 0, a f₃
(х)
=1, т. е. эти две функции не зависят от
х,
f₁
(х)
= х,
т. е. она не меняет аргумента.

Функция f₂
(х)
действительно содержательная функция.
Она принимает значения, противоположные
значениям аргумента, обозначается f₂
(х)=и называется отрицанием (читается “неx”)).

Набор значений переменных, на котором
функция принимает значение f
= 1, называетсяединичным набором
функцииf.Аналогично набор значений, на которомf = 0, называетсянулевым набором функции f,
В общем случае таблица истинности для
функции отп переменных должна иметь
2ⁿстрок.

Множество всех логических функций одной
переменной – унарные логические
операции– представлено в таблице
2. Число функцийР₂(1)==4.

Функции двух переменных

Множество всех логических функций двух
переменных – бинарные логические
операции– представлено в таблице .
Число функцийР₂(2)==16

Наиболее употребимые из этих функций
(только те, которые существенно зависят
от обеих переменных) мы приводим в
следующей таблице:

Перенумеруем и расположим их тоже в
естественном порядке.

1-2. Константы f₀
= 0 и f₁₅ =
1 являются константами.

3-6

Функции

являются по существу функциями одной
переменной.

Операция ОТРИЦАНИЕ — «логическое не»
— истинное высказывание превращает в
ложное и наоборот.

Инверсия логической
переменной истинна, если сама переменная
ложна, и, наоборот, инверсия ложна, если
переменная истинна.

7) конъюнкция
(функция И)

Заметим, что конъюнкция –
это фактически обычное умножение
(нулей и единиц). Иногда
эту функцию обозначают x&y
или xy;

• Определение Конъюнкциейnпеременных f (x₁, x₂,
  …,x_n) = x₁
  x₂…x_n называется
  функция, которая принимает значение
  1, если и только если все переменные
  равны 1 (и, значит, равна 0, если
  хотя бы одна из этих переменных равна
  0).

Конъюнкция двух высказываний
истинна тогда и только тогда, когда
истинны оба высказывания.

Операцию КОН’ЮНКЦИЯ называют еще
«логическим и».

дизъюнкция
(функция или)

• Определение Дизъюнкциейnпеременных f (x₁,x₂,
  …, x_n) =x_1Ú x_2Ú
  … Úx_nназывается такая
  функция, которая равна 0 если и только
  если все переменные равны 0 (и, значит,
  равна 1 тогда и только тогда, когда хотя
  бы одна переменная равна 1).

Операцию ДИЗ’ЮНКЦИЯ называют еще
«логическим или». Если два высказывания
соединить диз’юнкцией, то получится
сложное высказывание которое истинно,
если истинно хотя бы одно из входящих
в него высказываний.

Например, «Мы любим пиво или мы
любим мороженое» истинное сложное
высказывание, поскольку хотя бы одно
из входящих в него элементарных
высказываний истинно. А возможно,и оба.

Дизъюнкция двух высказываний
ложна тогда и только тогда, когда ложны
оба высказывания.

9-12) импликация
(следование)

Иногда импликацию обозначают
x  y   
(читается “из x
следует y”).

операция — это ИМПЛИКАЦИЯ или «логическое
если… , то».

Например, «Если Наполеон родился
в Кудымкаре, то газ при нагревании
сужается». Это, кстати, истинное
высказывание! Нет причин считать его
ложным.

Единственная ситуация, когда импликация
ложна, это когда посылка (часть

«если») истинна, а следствие (часть
«то») ложна.

Импликацию иногда (не совсем корректно
по иным причинам!) называют операцией
логического следования, хотя наш
пример показывает, что высказывания
могут логически не следовать одно из
другого, более того, могут не иметь
между собой никакой логической связи.
Напомним, импликация, как и другие
операции,

берет в расчет только истинность входящих
в нее высказываний.

«Если Волга впадает в Каспийское
море, то 2 + 2 = 4» истинное высказывание.

«Если Волга впадает в Каспийское
море, то 2 + 2 = 5» ложное высказывание.

Хотя оба эти «логические
рассуждения» с точки зрения здравого
рассуждения одинаково бессмысленны

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

«ЕСЛИ стоит хорошая погода, ТО мы
купаемся» и

«НЕВЕРНО, что стоит хорошая погода,
ИЛИ мы купаемся».

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

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

ИЗ ИСТИНЫ НЕ МОЖЕТ СЛЕДОВАТЬ
ЛОЖЬ

Это очень важная функция,
особенно в логике. Ее можно рассматривать
следующим образом: если х
= 0 (т. е. х
“ложно”), то из этого
факта можно вывести и “ложь”, и “истину”
(и это будет правильно), если у
= 1 (т. е. у
“истинно”), то истина
выводится и из “лжи” и из “истины”, и
это тоже правильно. Только вывод “из
истины ложь” является неверным. Заметим,
что любая теорема
всегда фактически
содержит эту логическую функцию;

13) сложение
по модулю 2 (здесь и
далее, если не оговорено противное,
знаком “+” мы будем обозначать такое
сложение):

14) эквивалентность
или подобие

Есть также ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ
или «тогда и только тогда»
Результирующее сложное высказывание
истинно, если одновременно истинны или
ложны оба входящих в него высказывания.

Эквивалентность двух
высказываний истинна только в тех
случаях, когда оба высказывания ложны
или оба истинны.

Эта f₉
= 1 тогда и только
тогда, когда х = у.

15) штрих
Шеффера

Иногда эту функцию называют “не и”
(так как она равна отрицанию конъюнкции);

ШТРИХ ШЕФФЕРА или логическое «и-не».
Результат этой операции равносилен
последовательному применению операций
кон’юнкции и отрицания. Соответственно,
результирующее высказывание будет
ложным, только если входящие в него
высказывания одновременно истинны.

Штрих Шеффера — этооперация замечательная
тем, что ее одной (необходимое количество
раз примененной) достаточно, чтобы
записать любое сложное высказывание.

• ЗамечаниеПри использовании логики
  для проектирования логических схем,
  например отдельных фрагментов
  процессора, первоначально эксплуатировали
  аналогию с релейными схемами. Операция
  диз’юнкции («или») соответствует
  параллельному подключению контактов
  реле, кон’юнкции («и») —
  последовательному. Операция отрицания
  («не») моделируется нормально
  замкнутым контактом реле.

• То есть контакт размыкается при
  срабатывании реле. Тогда достаточно
  было выпустить, например, модули типа
  «и-не», чтобы на них реализовать
  любую схему.

16) стрелка
Пирса (иногда эту
функцию называют штрих Лукасевича)

Эта функция является отрицанием
дизъюнкции и поэтому иногда ее называют
“не или”.

Три оставшиеся функции, (f₂
, f₄
и f₁₁)
запрет имликации и импликация
особого
значения в дискретной математике не
имеют.

Заметим, что часто будут
рассматриваться функции от функций,
т. е. суперпозиции
перечисленных выше
функций. При этом последовательность
действий указывается (как обычно)
скобками.

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

• Пример.Cоставить
  таблицу истинности функции трех
  переменных, заданной формулой:f(х₁,х₂,х₃)=()(x₁&x₃).

Для построения таблицы истинности fвычислим ее значения на каждом из восьми
наборов значений .

Свойства
конъюнкции, дизъюнкции и отрицания

1. Конъюнкция и дизъюнкция коммутативны,
т. е. обе функции не зависят от
порядка переменных.

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

«Мэри вышла замуж И родила ребенка»
равносильно с точки

зрения логики тому что «Мэри родила
ребенка И вышла замуж».

Семантика влияет.

Перестановка не соответствует общепринятой
морали — для приличного общества
существенно, какое событие стоит
первым. (Это в очередной раз говорит о
том, что

математическая логика не учитывает
[и не в состоянии это сделать!] многих
нюансов, имеющих место в практике жизни).

Законы
булевой алгебры

Универсальные границы:

x1 = 1; x0
=х;х1 =х;х0
= 0.

3. Ассоциативность конъюнкции и
дизъюнкции:

x(yz) = (xy)z;x
(y z) = (x
y)z.

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

Ассоциативный закон утверждает, что
безразлично, в каком порядке мы
рассматриваем (истинность) попарных
кон’юнкций и диз’юнкций:

«Стоит хорошая погода И мы купаемся
И заработали ангину».

«Стоит хорошая погода ИЛИ мы купаемся
ИЛИ заработали ангину».

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

4. Поглощение(“целое поглощает
часть”):

х ху=х(1у) =х.

5. Два распределительных закона:

х (y z) =x y  x z;х
(y z) = (x
y)(x z),

6. Правила де Моргана:

или
обобщая

Следующие 3 правила
доказываются на основе законов
дистрибутивности, противоречия и
«исключенного третьего».

13. Поглощение ( элиминация ) :

14. Закон Блейка-Порецкого :

15. Склеивание ( объединение ) :

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

Скачать материал

Скачать материал

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Существенные и фиктивные переменные

• 

  2 слайд

  Определение
  Говорят, что булева функция f(x1, …, xi, …, xn) существенно зависит от переменной xi, если выполняется условие:
  f(x1, …, xi-1,0,xi+1, …, xn) ≠ f(x1, …, xi-1,1,xi+1, …, xn).
  В этом случае также говорят, что переменная xi  существенная, в противном случае ее называют фиктивной переменной.
  Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции

• 

  3 слайд

  Пример 1. Рассмотрим булеву функцию f(x1, x2, x3) и исследуем ее переменные x1 и x3.
  Из таблиц истинности видно, что переменная x1 функции f(x1, x2, x3) существенная, так как f(0,x2, x3) ≠ f(1,x2, x3). Переменная x3 фиктивная, так как f(x1, x2, 0) = f(x1, x2, 1).

• 

  4 слайд

  Алгоритм распознавания фиктивной переменной по таблице истинности.
  – Для переменной x1 сравниваются половины столбца значений функции: верхняя и нижняя, так как именно в верхней половине x1=0, а в нижней x1=1, если они совпадают, то переменная x1 фиктивна;
  – для переменной x2 сравниваются четвертины столбца в каждой половине, так как именно в верхних четвертинах x2 =0, а в нижних x2 =1, если четвертины в каждой половине совпадают, то переменная x2 фиктивна;
  – и так далее (за четвертинами следуют 1/8, 1/16, … ).

• 

  5 слайд

  Пример 1. Булева функция f(x1, x2, x3)
  Переменная x1 существенна, так как верхняя половина столбца значений функции (0011) не равна нижней половине (1100).
  Переменная x2 существенна, так как четвертины уже в первой половине различаются (00 и 11).
  Переменная x3 фиктивна, так как осьмушки во всех четвертинах равны (0 и 0, 1 и 1, 1 и 1, 0 и 0).

• 

  6 слайд

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

• 

  7 слайд

  Алгоритм удаления фиктивной переменной
  Алгоритм удаления фиктивной переменной xi состоит в вычеркивании из таблицы истинности всех строк, в которых xi = 0 (или всех строк, в которых xi = 1), и столбца xi.
  Пример (функция та же). Применив алгоритм для удаления фиктивной переменой x3, получаем результат

• 

  8 слайд

  Пример
  Определение. 
  Булевы функции назовем равными с точностью до фиктивных переменных, если равны функции, полученные из исходных удалением фиктивных переменных
  Рассмотрим функции f1(x1, x2) и f2(x1, x2).
  Удалив фиктивную переменную x1 функции f1(x1, x2) и фиктивную переменную x2 функции f2(x1, x2), получим равные функции f1(x2)=f2(x1)=f(x).
  Значит, исходные функции равны с точностью до фиктивных переменных.

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 265 919 материалов в базе

• Выберите категорию:

• Выберите учебник и тему

• Выберите класс:

• Тип материала:

  • Все материалы

  • Статьи

  • Научные работы

  • Видеоуроки

  • Презентации

  • Конспекты

  • Тесты

  • Рабочие программы

  • Другие методич. материалы

Найти материалы

Вам будут интересны эти курсы:

• Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»

• Курс повышения квалификации «Педагогическое проектирование как средство оптимизации труда учителя математики в условиях ФГОС второго поколения»

• Курс повышения квалификации «Изучение вероятностно-стохастической линии в школьном курсе математики в условиях перехода к новым образовательным стандартам»

• Курс профессиональной переподготовки «Экономика: теория и методика преподавания в образовательной организации»

• Курс повышения квалификации «Специфика преподавания основ финансовой грамотности в общеобразовательной школе»

• Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»

• Курс повышения квалификации «Особенности подготовки к сдаче ОГЭ по математике в условиях реализации ФГОС ООО»

• Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»

• Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»

• Курс профессиональной переподготовки «Инженерная графика: теория и методика преподавания в образовательной организации»

• Курс повышения квалификации «Методика преподавания курса «Шахматы» в общеобразовательных организациях в рамках ФГОС НОО»

• Курс повышения квалификации «Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО»

• Курс профессиональной переподготовки «Черчение: теория и методика преподавания в образовательной организации»