Контактная схема - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:35Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:21, 1 сентября 2022

2022-09-01T05:21:47Z

94.25.228.234: Опечатка

2019-10-09T22:11:48Z

Опечатка

91.122.59.144: /* Принцип работы */

2017-10-12T21:42:17Z

‎Принцип работы

91.122.59.144: /* Принцип работы */

2017-10-12T21:41:06Z

‎Принцип работы

109.251.113.129: /* Построение контактных схем */

2015-03-30T13:29:22Z

‎Построение контактных схем

Lapenok.aleksej: /* Задача о минимизации контактной схемы */

2014-11-17T17:37:38Z

‎Задача о минимизации контактной схемы

Shersh в 17:30, 17 ноября 2014

2014-11-17T17:30:20Z

Shersh в 17:30, 17 ноября 2014

2014-11-17T17:30:07Z

5.18.162.227: /* Задача о минимизации контактной схемы */

2014-11-16T10:33:36Z

‎Задача о минимизации контактной схемы

← Предыдущая		Версия 16:21, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.		Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.
	{{Определение		{{Определение

← Предыдущая		Версия 05:21, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.		Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.
	{{Определение		{{Определение

@@ Строка 74: / Строка 74: @@
 {{Теорема
-|statement = Любой булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
+|statement = Любую булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
 |proof =
 Пусть дана функция <tex>f(x_1,x_2 \dots, x_n)</tex> и она представлена в [[ДНФ|ДНФ]]

@@ Строка 18: / Строка 18: @@
 {{Определение
 |definition =
-'''Разомкнутый контакт''' (англ. ''open contact'') {{---}} контакт схемы, над которым написана <tex>0</tex> или значение переменной равно <tex>0</tex>.
+'''Разомкнутый контакт''' (англ. ''open contact'') {{---}} контакт схемы, над которым написан <tex>0</tex> или значение переменной равно <tex>0</tex>.
 }}

@@ Строка 13: / Строка 13: @@
 {{Определение
 |definition =
-'''Замкнутый контакт''' (англ. ''closed contact'') {{---}} контакт схемы, над которым написана <tex>0</tex> или значение переменной равно <tex>0</tex>.
+'''Замкнутый контакт''' (англ. ''closed contact'') {{---}} контакт схемы, над которым написана <tex>1</tex> или значение переменной равно <tex>1</tex>.
 }}
 {{Определение
 |definition =
-'''Разомкнутый контакт''' (англ. ''open contact'') {{---}} контакт схемы, над которым написана <tex>1</tex> или значение переменной равно <tex>1</tex>.
+'''Разомкнутый контакт''' (англ. ''open contact'') {{---}} контакт схемы, над которым написана <tex>0</tex> или значение переменной равно <tex>0</tex>.
 }}
-Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы (из вершины <tex>u</tex> ребра только выходят, в вершину <tex>v</tex> ребра только входят), определяющую функцию <tex>g(x_1, x_2 \dots, x_n)</tex>. Тогда <tex>g(x_1, x_2 \dots, x_n)</tex> принимает значение <tex>1</tex> при таком наборе значений переменных, если можно добраться из <tex>u</tex> в <tex>v</tex> только по разомкнутым контактам.
+Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы (из вершины <tex>u</tex> ребра только выходят, в вершину <tex>v</tex> ребра только входят), определяющую функцию <tex>g(x_1, x_2 \dots, x_n)</tex>. Тогда <tex>g(x_1, x_2 \dots, x_n)</tex> принимает значение <tex>1</tex> при таком наборе значений переменных, если можно добраться из <tex>u</tex> в <tex>v</tex> только по замкнутым контактам.
 ==Построение контактных схем==

@@ Строка 34: / Строка 34: @@
 Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует.
-В качестве примера рассмотрим функцию, представленную в [[ДНФ|ДНФ]]: <tex>f=(\neg x \land y \land \neg z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z)</tex>. Каждой скобке [[ДНФ|ДНФ]] соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена ниже.
+В качестве примера рассмотрим функцию, представленную в [[ДНФ|ДНФ]]: <tex>f=(\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land z)</tex>. Каждой скобке [[ДНФ|ДНФ]] соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена ниже.
 [[Файл:example10.png|320px]]

@@ Строка 64: / Строка 64: @@
 {{Определение
 |definition =
-'''Дерево конъюнктов для <tex>n</tex> переменных''' {{---}} двоичное ориентированное дерево глубиной <tex>n</tex>, такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной <tex>x_k (k<=n)</tex>, а правое помечено символом отрицания переменной <tex>x_k</tex>.
+'''Дерево конъюнктов для <tex>n</tex> переменных''' {{---}} двоичное ориентированное дерево глубиной <tex>n</tex>, такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной <tex>x_k (k \leqslant n)</tex>, а правое помечено символом отрицания переменной <tex>x_k</tex>.
 }}
@@ Строка 79: / Строка 79: @@
 [[Файл:tree_for_two.png | 250px | thumb | Дерево конъюнктов для 2-х переменных]]
-Возьму дерево конъюнктов для <tex>n</tex> переменных (см. картинку). Очевидно, что от вершины <tex>u</tex> до "нижних" вершин дерево можно добраться за <tex>O(n)</tex>, а ребер у такого дерева <tex>O(2^n)</tex>
+Возьмем дерево конъюнктов для <tex>n</tex> переменных (см. картинку). Очевидно, что от вершины <tex>u</tex> до "нижних" вершин дерево можно добраться за <tex>O(n)</tex>, а ребер у такого дерева <tex>O(2^n)</tex>
 Соединим нижние вершины, которые соответствуют конъюнктам функции, с вершиной <tex>v</tex> контактами, над которыми написана <tex>1</tex>. От этого в схему добавится не более, чем <tex>2^n</tex> ребер и тогда сложность останется <tex>O(2^n)</tex>.

@@ Строка 8: / Строка 8: @@
 '''Контакт''' (англ. ''contact'') {{---}} ребро схемы, помеченное символом переменной или ее отрицанием. Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)
 }}
 ==Принцип работы==

@@ Строка 62: / Строка 62: @@
 {{Определение
 |definition='''Минимальная контактная схема''' (англ. ''minimal contact circuit'') {{---}} схема, имеющая наименьшую сложность среди эквивалентных ей схем.
 }}