当前位置：网站首页>[mathematical logic] predicate logic (predicate logic basic equivalent | eliminate quantifier equivalent | quantifier negative equivalent | quantifier scope contraction expansion equivalent | quantifi
[mathematical logic] predicate logic (predicate logic basic equivalent | eliminate quantifier equivalent | quantifier negative equivalent | quantifier scope contraction expansion equivalent | quantifi
2022-07-03 03:53:00 【Programmer community】
List of articles
- One 、 Eliminate quantifiers Equivalent formula
- Two 、 Quantifier negation Equivalent formula
- 3、 ... and 、 The scope of quantifiers shrinks and expands Equivalent formula
- Four 、 Quantifier assignment Equivalent formula
One 、 Eliminate quantifiers Equivalent formula
Eliminate quantifier equivalents :
Finite individual field
D
=
{
a
1
,
a
2
,
⋯
,
a
n
}
D = \{a_1 , a_2 , \cdots , a_n\}
D={ a1,a2,⋯,an} , Eliminate quantifiers Of Equivalent formula :
Finite individual field eliminate Full name quantifier :
∀
x
A
(
x
)
⇔
A
(
a
1
)
∧
A
(
a
2
)
∧
⋯
∧
A
(
a
n
)
\forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n)
∀xA(x)⇔A(a1)∧A(a2)∧⋯∧A(an)
Finite individual field eliminate There are quantifiers :
∃
x
A
(
x
)
⇔
A
(
a
1
)
∨
A
(
a
2
)
∨
⋯
∨
A
(
a
n
)
\exist x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)
∃xA(x)⇔A(a1)∨A(a2)∨⋯∨A(an)
Be sure to pay attention to the premise : Finite individual field ;
When the individual domain is infinite , You need quantifiers , Such as Total individual domain ;
Two 、 Quantifier negation Equivalent formula
Negative full quantifier : Full name quantifier
∀
\forall
∀ Before Of Negative connectives , Can be moved to quantifiers after , Quantifiers should become There are quantifiers
∃
\exist
∃ ;
¬
∀
x
A
(
x
)
⇔
∃
x
¬
A
(
x
)
\lnot \forall x A(x) \Leftrightarrow \exist x \lnot A(x)
¬∀xA(x)⇔∃x¬A(x)
Equivalent interpretation :
¬
∀
x
A
(
x
)
\lnot \forall x A(x)
¬∀xA(x) : Not all
x
x
x All have properties
A
A
A ;
∃
x
¬
A
(
x
)
\exist x \lnot A(x)
∃x¬A(x) : There is
x
x
x Not of a nature
A
A
A ;
- The above two formulas are equivalent ;
Negative existential quantifiers : There are quantifiers
∃
\exist
∃ Before Of Negative connectives , Can be moved to quantifiers after , Quantifiers should become Full name quantifier
∀
\forall
∀ ;
¬
∃
x
A
(
x
)
⇔
∀
x
¬
A
(
x
)
\lnot \exist x A(x) \Leftrightarrow \forall x \lnot A(x)
¬∃xA(x)⇔∀x¬A(x)
Equivalent interpretation :
¬
∃
x
A
(
x
)
\lnot \exist x A(x)
¬∃xA(x) : non-existent
x
x
x Have the quality of
A
A
A ;
∀
x
¬
A
(
x
)
\forall x \lnot A(x)
∀x¬A(x) : be-all
x
x
x Have no nature
A
A
A ;
- The above two formulas are equivalent ;
3、 ... and 、 The scope of quantifiers shrinks and expands Equivalent formula
hypothesis
B
B
B It's the formula ,
B
B
B It does not contain
x
x
x ( Premise is very important ) ;
1. Full name quantifier The scope shrinks and expands ( Disjunctive connectives ) :
∀
x
(
A
(
x
)
∨
B
)
⇔
∀
x
A
(
x
)
∨
B
\forall x ( A(x) \lor B ) \Leftrightarrow \forall x A(x) \lor B
∀x(A(x)∨B)⇔∀xA(x)∨B
- The full quantifier on the left
∀
x
\forall x
∀x Our jurisdiction is
(
A
(
x
)
∨
B
)
( A(x) \lor B )
(A(x)∨B)
- The full quantifier on the right
∀
x
\forall x
∀x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
A
(
x
)
∨
B
)
( A(x) \lor B )
(A(x)∨B) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
A
(
x
)
∨
B
)
( A(x) \lor B )
(A(x)∨B)
2. There are quantifiers The scope shrinks and expands ( Disjunctive connectives ) :
∃
x
(
A
(
x
)
∨
B
)
⇔
∃
x
A
(
x
)
∨
B
\exist x ( A(x) \lor B ) \Leftrightarrow \exist x A(x) \lor B
∃x(A(x)∨B)⇔∃xA(x)∨B
- The existential quantifier on the left
∃
x
\exist x
∃x Our jurisdiction is
(
A
(
x
)
∨
B
)
( A(x) \lor B )
(A(x)∨B)
- The existential quantifier on the right
∃
x
\exist x
∃x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
A
(
x
)
∨
B
)
( A(x) \lor B )
(A(x)∨B) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
A
(
x
)
∨
B
)
( A(x) \lor B )
(A(x)∨B)
3. Full name quantifier The scope shrinks and expands ( Conjunctions ) :
∀
x
(
A
(
x
)
∧
B
)
⇔
∀
x
A
(
x
)
∧
B
\forall x ( A(x) \land B ) \Leftrightarrow \forall x A(x) \land B
∀x(A(x)∧B)⇔∀xA(x)∧B
- The full quantifier on the left
∀
x
\forall x
∀x Our jurisdiction is
(
A
(
x
)
∧
B
)
( A(x) \land B )
(A(x)∧B)
- The full quantifier on the right
∀
x
\forall x
∀x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
A
(
x
)
∧
B
)
( A(x) \land B )
(A(x)∧B) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
A
(
x
)
∧
B
)
( A(x) \land B )
(A(x)∧B)
4. There are quantifiers The scope shrinks and expands ( Conjunctions ) :
∃
x
(
A
(
x
)
∧
B
)
⇔
∃
x
A
(
x
)
∧
B
\exist x ( A(x) \land B ) \Leftrightarrow \exist x A(x) \land B
∃x(A(x)∧B)⇔∃xA(x)∧B
- The existential quantifier on the left
∃
x
\exist x
∃x Our jurisdiction is
(
A
(
x
)
∧
B
)
( A(x) \land B )
(A(x)∧B)
- The existential quantifier on the right
∃
x
\exist x
∃x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
A
(
x
)
∧
B
)
( A(x) \land B )
(A(x)∧B) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
A
(
x
)
∧
B
)
( A(x) \land B )
(A(x)∧B)
5. Full name quantifier The scope shrinks and expands ( Contains connectives B On the right ) :
∀
x
(
A
(
x
)
→
B
)
⇔
∃
x
A
(
x
)
→
B
\forall x ( A(x) \to B ) \Leftrightarrow \exist x A(x) \to B
∀x(A(x)→B)⇔∃xA(x)→B
- The full quantifier on the left
∀
x
\forall x
∀x Our jurisdiction is
(
A
(
x
)
→
B
)
( A(x) \to B )
(A(x)→B)
- The existential quantifier on the right
∃
x
\exist x
∃x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
A
(
x
)
→
B
)
( A(x) \to B )
(A(x)→B) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
A
(
x
)
→
B
)
( A(x) \to B )
(A(x)→B)
6. There are quantifiers The scope shrinks and expands ( Contains connectives B On the right ) :
∃
x
(
A
(
x
)
→
B
)
⇔
∀
x
A
(
x
)
→
B
\exist x ( A(x) \to B ) \Leftrightarrow \forall x A(x) \to B
∃x(A(x)→B)⇔∀xA(x)→B
- The existential quantifier on the left
∃
x
\exist x
∃x Our jurisdiction is
(
A
(
x
)
→
B
)
( A(x) \to B )
(A(x)→B)
- The full quantifier on the right
∀
x
\forall x
∀x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
A
(
x
)
→
B
)
( A(x) \to B )
(A(x)→B) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
A
(
x
)
→
B
)
( A(x) \to B )
(A(x)→B)
( Use Implication equivalence elimination Contains connectives Can prove that )
7. Full name quantifier The scope shrinks and expands ( Contains connectives B On the left ) :
∀
x
(
B
→
A
(
x
)
)
⇔
B
→
∀
x
A
(
x
)
\forall x ( B \to A(x) ) \Leftrightarrow B \to \forall x A(x)
∀x(B→A(x))⇔B→∀xA(x)
- The full quantifier on the left
∀
x
\forall x
∀x Our jurisdiction is
(
B
→
A
(
x
)
)
( B \to A(x) )
(B→A(x))
- The full quantifier on the right
∀
x
\forall x
∀x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
B
→
A
(
x
)
)
( B \to A(x) )
(B→A(x)) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
B
→
A
(
x
)
)
( B \to A(x) )
(B→A(x))
8. There are quantifiers The scope shrinks and expands ( Contains connectives B On the left ) :
∃
x
(
B
→
A
(
x
)
)
⇔
B
→
∃
x
A
(
x
)
\exist x ( B \to A(x) ) \Leftrightarrow B \to \exist x A(x)
∃x(B→A(x))⇔B→∃xA(x)
- The existential quantifier on the left
∃
x
\exist x
∃x Our jurisdiction is
(
B
→
A
(
x
)
)
( B \to A(x) )
(B→A(x))
- The existential quantifier on the right
∃
x
\exist x
∃x Our jurisdiction is
A
(
x
)
A(x)
A(x)
- From left to right : Jurisdiction by
(
B
→
A
(
x
)
)
( B \to A(x) )
(B→A(x)) Shrink to
A
(
x
)
A(x)
A(x)
- From right to left : Jurisdiction by
A
(
x
)
A(x)
A(x) Expand into
(
B
→
A
(
x
)
)
( B \to A(x) )
(B→A(x))
Four 、 Quantifier assignment Equivalent formula
1. Full name quantifier about Syntaxis
∧
\land
∧ Distribution rate :
∀
x
(
A
(
x
)
∧
B
(
x
)
)
⇔
∀
x
A
(
x
)
∧
∀
x
B
(
x
)
\forall x ( A(x) \land B(x) ) \Leftrightarrow \forall x A(x) \land \forall x B(x)
∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)
understand : All objects have
A
,
B
A , B
A,B Two properties , Equivalent to All objects have
A
A
A nature and All objects have
B
B
B nature ;
Save all weighing words about Conjunctions
∧
\land
∧ There is a distribution rate , about Disjunctive connectives
∨
\lor
∨ Not suitable for distribution rate ;
2. There are quantifiers about Disjunction
∨
\lor
∨ Distribution rate :
∃
x
(
A
(
x
)
∨
B
(
x
)
)
⇔
∃
x
A
(
x
)
∨
∃
x
B
(
x
)
\exist x ( A(x) \lor B(x) ) \Leftrightarrow \exist x A(x) \lor \exist x B(x)
∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)
understand : Objects exist Or there is
A
A
A nature , Or there is
B
B
B nature ;
There are quantifiers about Disjunctive connectives
∨
\lor
∨ There is a distribution rate , about Conjunctions
∧
\land
∧ Not suitable for distribution rate ;
边栏推荐
- Basic operations of mongodb [add, delete, modify, query]
- CEPH Shangwen network xUP Nange that releases the power of data
- 第十届中国云计算大会·中国站：展望未来十年科技走向
- [MySQL] the difference between left join, right join and join
- Mysql Mac版下载安装教程
- numpy之 警告VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences
- 2022 tea master (intermediate) examination questions and analysis and tea master (intermediate) practical examination video
- PHP generates PDF tcpdf
- Message queue addition failure
- [Blue Bridge Road -- bug free code] DS18B20 temperature reading code analysis
猜你喜欢
Numpy warning visibledeprecationwarning: creating an ndarray from ragged needed sequences
SAP UI5 应用开发教程之一百零五 - SAP UI5 Master-Detail 布局模式的联动效果实现明细介绍
Wechat applet + Alibaba IOT platform + Hezhou air724ug build a serverless IOT system (III) -- wechat applet is directly connected to Alibaba IOT platform aliiot
Recursion: quick sort, merge sort and heap sort
2022 tea master (primary) examination questions and tea master (primary) examination question bank
递归：快速排序，归并排序和堆排序
Hutool dynamically adds scheduled tasks
NPM: the 'NPM' item cannot be recognized as the name of a cmdlet, function, script file, or runnable program. Please check the spelling of the name. If the path is included, make sure the path is corr
中移物联网OneOS与OneNET入选《2021年物联网示范项目名单》
105. Detailed introduction of linkage effect realization of SAP ui5 master detail layout mode
随机推荐
Docker install and start MySQL service
Role of JS No
[Apple Push] IMessage group sending condition document (push certificate) development tool pushnotification
Intercept string fixed length to array
redis在服务器linux下的启动的相关命令（安装和配置）
Commands related to the startup of redis under Linux server (installation and configuration)
2022 polymerization process examination questions and polymerization process examination skills
C语言HashTable/HashSet库汇总
What is pytorch? Is pytorch a software?
Cnopendata China Customs Statistics
For instruction, uploading pictures and display effect optimization of simple wechat applet development
Applet get user avatar and nickname
ffmpeg下载安装教程及介绍
Web会话管理安全问题
shardingsphere动态数据源
Dynamic programming: Longest palindrome substring and subsequence
Debug: CD cannot be used in kaggle
Recursion: depth first search
如何迈向IPv6之IPv6过渡技术-尚文网络奎哥
Introduction to mongodb