数理逻辑—范式

简介: 数理逻辑—范式

正文


简单析取式与简单合取式


定义:

仅由有限个命题变项或其否定构成的析取式称为简单析取式。仅由有限个命题变项或其否定构成的合取式称为简单合取式


例如:

p、¬ p、p ∨ q 、p ∨ ¬ q 、¬ p ∨ q ∨ rr等都是简单析取式;

p 、¬ p 、p ∧ q、p ∧ ¬ q、¬ p ∧ q ∧ r 等都是简单合取式。


由以上定义可以得到两点结论:

  1. 一个简单析取式重言式,当且仅当它同时含有一个命题变项及其否定;
  2. 一个简单合取式矛盾式,当且仅当它同时含有一个命题变项及其否定。



例如:

简单析取式p ∨ ¬ q ∨ q 是重言式;简单合取式p ∧ ¬ q ∧ q 是矛盾式。



析取范式与合取范式


定义:

仅由有限个简单合取式构成的析取式称为析取范式;仅由有限个简单析取式构成的合取式称为合取范式


例如:

p∨q∨¬r、¬ p ∨ ¬ q ∨ r、( p 1 ∧ ¬ q 1 ) ∨ ( ¬ p 1 ∧ p 2 ) ∨ ( p 1 ∧ p 2 ∧ p 3 ) 是析取范式;

p ∧ q ∧ ¬ r 、¬ p ∧ ¬ q ∧ r 、( p 1 ∨ ¬ q 1 ) ∧ ( ¬ p 1 ∨ p 2 ) ∧ ( p 1 ∨ p 2 ∨ p 3 )是合取范式;


由以上定义可以得到两点结论:


一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式;

一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式。


范式存在定理与范式求解


范式存在定理:

任一命题公式都存在着不唯一的与之等值的析取范式和合取范式。


根据范式存在定理,可知任一命题公式都能通过等值演算求出与之等值的析取范式与合取范式。步骤如下:


消去→ 和↔:

p → q ;⟺  ¬ p ∨ q

p ↔ q ⟺  ( ¬ p ∨ q ) ∧ ( p ∨ ¬ q )


否定号的消去或内移:

¬¬p⟺q¬ ( p ∧ q )

¬ p ∨ ¬ q⟺¬p∨¬q

¬ ( p ∨ q ) ⟺¬ p ∧ ¬ q


使用分配率。对析取范式应使用∧对∨的分配率;对合取范式应使用∨对∧的分配率。

举例:求( ( p ∨ q ) → r ) → p的合取范式和析取范式

解:

0000000000000000.png


主析取范式与主合取范式


定义:

如果公式A 的析取范式中的简单合取式全是极小项,则称该析取范式为主析取范式;如果公式A 的合取范式中的简单析取式全是极大项,则称该合取范式为主合取范式。


极小项与极大项


极小项定义:

在有n 个命题变项的简单合取式中,若每个命题变项及其否定有且仅有其中一个出现一次,则称这样的简单合取式为极小项。


通常极小项的命题变项用1表示,命题变项的否定用0表示,这就组成了一段二进制码,按二进制码的大小进行排序后用小写字母m ( m i n i m u m ) 加从0开始递增的脚标命名,例:m 0 、m 1

例如:2个命题变项p 、q 可形成4个极小项;3个命题变项r 、s 、t 可形成8个极小项


000000000000.png

极大项定义:

在有n 个命题变项的简单析取式中,若每个命题变项及其否定有且仅有其中一个出现一次,则称这样的简单析取式为极大项。

通常极大项的命题变项用0表示,命题变项的否定用1表示,这就组成了一段二进制码,按二进制码的大小进行排序后用大写字母m ( m a x i m u m ) 加从0开始递增的脚标命名,例:m 0 、m 1

例如:2个命题变项p 、q 可形成4个极小项;3个命题变项r 、s 、t 可形成8个极大项

000000000.png


主范式存在定理:

任何命题公式都有唯一的主析取范式或主合取范式。


求解主范式的步骤:


求出析取范式或合取范式

扩展命题变项,将简单合取式(简单析取式)扩展为极小项(极大项)形式

合并重复项

求余项,求出主析取范式后余下的项就是主合取范式的组成项,求出主合取范式后余下的项就是主析取范式的组成项


例如:求( ( p ∨ q ) → r ) → p的主析取范式与主合取范式主范式

解:

0000000.png00000.png

相关文章
|
消息中间件 存储 开发者
实现AMQP的高效消息传递机制
【8月更文第28天】高级消息队列协议 (AMQP) 是一个为消息中间件设计的开放标准应用层协议。它为消息传递系统提供了标准化的方法,从而确保了高性能和可靠性。本文将详细介绍AMQP中的一些关键特性,并通过示例代码展示如何利用这些特性。
360 2
|
10月前
|
消息中间件 Java 开发工具
【实践】快速学会使用云消息队列RabbitMQ版
本次分享的主题是快速学会使用云消息队列RabbitMQ版的实践。内容包括:如何创建和配置RabbitMQ实例,如Vhost、Exchange、Queue等;如何通过阿里云控制台管理静态用户名密码和AccessKey;以及如何使用RabbitMQ开源客户端进行消息生产和消费测试。最后介绍了实验资源的回收步骤,确保资源合理利用。通过详细的操作指南,帮助用户快速上手并掌握RabbitMQ的使用方法。
781 10
|
7月前
|
存储 SQL 缓存
StarRocks 存算分离在京东物流的落地实践
本文分享了京东物流在StarRocks存算分离架构上的实践与成果。通过将UData平台从存算一体升级为存算分离,显著提升了查询性能和资源利用率,同时大幅降低了存储成本(90%)和计算资源成本(30%)。文章详细介绍了存算分离的背景、部署方案、性能表现及优化措施,包括联邦查询、实时写入、Compaction调优等关键技术点。未来,京东物流将持续推动存算分离的应用拓展,并探索更多降本增效策略,如Stream Load任务合并与主动缓存管理。
|
8月前
|
人工智能 自然语言处理 程序员
无编程经验小白如何玩转通义灵码 AI 程序员,让写代码像聊天一样简单
没有编程经验的小白如何玩转通义灵码 AI 程序员,让写代码像聊天一样简单
1917 24
|
测试技术 Python
多种方法实现Appium屏幕滑动:让用户仿真动作更简单
本文介绍了Appium在移动端自动化测试中如何模拟用户滑动操作。滑动常见于触摸事件模拟,坐标计算和惯性滑动场景。Appium提供了`swipe`和`scroll`两种方法:`swipe`需要指定起始和结束坐标及可选的持续时间;`scroll`则直接使用起始和结束元素进行滑动。文中给出了Python示例代码,展示了如何在不同场景下执行滑动操作。
|
SQL 存储 API
SqlAlchemy 2.0 中文文档(四十四)(6)
SqlAlchemy 2.0 中文文档(四十四)
270 4
LabVIEW创建自定义输入控件、显示控件和自定义类型2
LabVIEW创建自定义输入控件、显示控件和自定义类型2
604 2
|
消息中间件
RabbitMQ之mandatory和immediate
mandatory和immediate是AMQP协议中basic.publish方法中的两个标识位,它们都有当消息传递过程中不可达目的地时将消息返回给生产者的功能。对于刚开始接触RabbitMQ的朋友特别容易被这两个参数搞混,这里博主整理了写资料,简单讲解下这两个标识位。
298 0
|
SQL 关系型数据库 MySQL
达梦(DM) SQL基础操作
讲述达梦 DM数据库 SQL基础查询语句