当前位置：网站首页>[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 ;
边栏推荐
- C语言HashTable/HashSet库汇总
- 2022年已过半，得抓紧
- Half of 2022 is over, so we must hurry up
- pytorch项目怎么跑？
- 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
- 毕设-基于SSM宠物领养中心
- IPv6过渡技术-6to4手工隧道配置实验--尚文网络奎哥
- 2022 tea master (intermediate) examination questions and analysis and tea master (intermediate) practical examination video
- 学会pytorch能干什么？
- Intercept string fixed length to array
猜你喜欢
IPv6 transition technology-6to4 manual tunnel configuration experiment -- Kuige of Shangwen network
2022deepbrainchain biweekly report no. 104 (01.16-02.15)
Introduction to mongodb
Pytorch multi card distributed training distributeddataparallel usage
pytorch难学吗？如何学好pytorch？
第十届中国云计算大会·中国站：展望未来十年科技走向
Download and install captura and configure ffmpeg in captura
Mysql Mac版下载安装教程
Cnopendata China Customs Statistics
Introduction à mongodb
随机推荐
Ffmpeg download and installation tutorial and introduction
Read a paper_ ChineseBert
redis在服务器linux下的启动的相关命令（安装和配置）
TCP/IP模型中的重磅嘉宾TCP--尚文网络奎哥
How to move towards IPv6: IPv6 Transition Technology - Shangwen network quigo
Is pytorch difficult to learn? How to learn pytorch well?
Makefile demo
Web会话管理安全问题
递归：一维链表和数组
Use three JS make a simple 3D scene
MongoDB簡介
Introduction à mongodb
【刷题篇】多数元素（超级水王问题）
Mongodb replication set [master-slave replication]
Summary of electromagnetic spectrum
在 .NET 6 项目中使用 Startup.cs
简易版 微信小程序开发之页面跳转、数据绑定、获取用户信息、获取用户位置信息
Bisher - based on SSM pet adoption center
Download and install node, NPM and yarn
2.14 simulation summary