- 2024-08-102-SAT 学习笔记
2-SAT用于求解布尔方程组,其中每个方程最多含有两个变量,方程的形式为\((a∨b)=1\),即式子\(a\)为真或式子\(b\)为真。求解的方法是根据逻辑关系式建图,然后求强联通子图,每一个强联通子图的答案都是一样的。建图:这里以模版题为例:题意:给定若干个需要满足的条件,其形式为\(a,1
- 2024-07-302-SAT
为了方便理解,咱们可以先看一组实例。今天huge要买水果lbtl说:1.我不吃梨(\(\nega\))2.我吃苹果(b)3.我吃草莓(c)lxyt说:1.我吃梨(a)2.我吃苹果(b)3.我不吃草莓(\(\negc\))CTH说:1.我不吃梨(\(\nega\))2.我不吃苹果(\(\negb\))3.我不吃草莓(\(\negc\))(huge:不吃,滚)我们不妨根据逻辑
- 2024-06-04力扣-494. 目标和
1.题目题目地址(494.目标和-力扣(LeetCode))https://leetcode.cn/problems/target-sum/题目描述给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加 '+'或'-',然后串联起所有整数,可以构造一个表达式:例如,nums=[2,1],可以在2之前添加'+',
- 2024-05-30Chapter 4 证明技巧
证明技巧:思路图使用公理系统时,证明的「构思过程」与证明的「书写过程」大相径庭。思考过程往往从最后一步开始,逐步规约。来看两个例子传递律的证明\[A\rightarrowB,B\rightarrowC\vdashA\rightarrowC\]Thinking&Writing...换位律的证明\[\vdash(A\rightarrow(B\ri
- 2024-05-30Chapter 4 Problems
T1证明\(\negA\rightarrowB,\negA\rightarrow\negB\vdashA\)可用定理:\(\vdash(\negA\rightarrowA)\rightarrowA\)Proof\[\begin{aligned}A_1:\quad&\negA\rightarrowB&\in\Gamma\\A_2:\quad&\negA\rightarrow
- 2024-05-30幽夜默示录 Turorial
幽夜默示录解析没有爱就看不见P1直接构造前件为真,后件为假的情况即可。比如可令\(P(x,y)\)永真、\(Q(x,y)\)永假。P2构造时满足「对于任意的\(y\)」存在「不同的\(x\)」满足\(P(x,y)\)即可。比如\[P=\left(\begin{matrix}0&1\\1&0\end{matrix}\right)\]P3注
- 2024-05-03Chapter 3 Tutorials
T1用等值演算、构造指派等方式判断公式的永真性(1)判断永真性:\((\forallxP(x)\rightarrow\existxQ(x))\rightarrow\existx(P(x)\rightarrowQ(x))\)首先尝试转化前束范式\[\begin{aligned}&(\forallxP(x)\rightarrow\existxQ(x))\rightarrow\existx(P(x)
- 2024-05-01ZORICH数学分析
ZORICH数学分析CHAPTER1一些通用的数学概念与记号§1.逻辑符号1.关系与括号\[L\impliesP\\\text{表示L蕴含P}\]\[L\iffP\\\text{表示L与P等价}\]\[((L\impliesP)\land(\negP))\implies(\negL)\\\text{表示若P由L推出,而P不真,则L不真}\]\[\neg((L\iffG)\l
- 2024-04-25Week 9 Problems
T1用等值演算、构造指派等方式判断公式的永真性(1)\[(\forallxP(x)\rightarrow\existxQ(x))\rightarrow\existx(P(x)\rightarrowQ(x))\](2)\[(\forallxP(x)\rightarrow\forallxQ(x))\rightarrow\forallx(P(x)\rightarrowQ(x))\]T2以下哪一步出现错误?
- 2024-04-18Chapter 2 Tutorials
Chapter2ProblemsT1利用真值指派讨论证明形如\(Q\rightarrow(R\rightarrowQ)\)的命题逻辑合式公式是永真式解对于任意指派函数\(\sigma\),若\(\sigma(Q)=0\),则\[\begin{aligned}&\sigma\big(Q\rightarrow(R\rightarrowQ)\big)\\=&\sigma\big(0\rightarrow(R\rightarro
- 2024-04-10640. 求解方程(中)
目录题目题解:模拟题目求解一个给定的方程,将x以字符串"x=#value"的形式返回。该方程仅包含'+','-'操作,变量x和其对应系数。如果方程没有解或存在的解不为整数,请返回"Nosolution"。如果方程有无限解,则返回“Infinitesolutions”。题目保证,如果方程中只有一个解,则
- 2024-03-26Week 5 Problems
T5判断对错:任意命题合式公式可以等价转化为复杂度不超过二的形式T6(2)今有一命题逻辑合式公式\(F_2\)为\[(P\rightarrowR)\rightarrow((Q\rightarrowR)\rightarrow(P\lorQ)\land\negR)\]根据Week1T1(1)中真值表写出\(F_2\)的主析取范式与主合取范式T7设命题逻辑合
- 2024-03-21Chapter 1 Tutorials
T1今有一逻辑表达式\(F_0\)为:\[(p\rightarrowr)\rightarrow((q\rightarrowr)\rightarrow(p\lorq)\land\negr)\]其中的联结词运算优先级与命题逻辑合式公式完全相同。观察\(F_0\)的形式,完成以下两个题目(1)补全真值表pqr\(p\rightarrowr\)\(q\rightarrowr\)
- 2024-03-06Week 2 Problems
T1代换式、替换式求代换式\((P\rightarrow(P\rightarrowQ))[P/P\rightarrowR]\)求替换式\((P\lorR\rightarrowP\lorR\landS)[(P\lorR)/(P\landR)]\)已知\(P,Q,R,S\)是命题逻辑合式公式,\(P\)是\(Q\)的子公式,\(R\)不是\(Q\)的子公式,用\(Q^1\equivQ[P/R]\)和「替
- 2024-03-01Week 1 Problems
T1今有一逻辑表达式\(F_0\)为:\[(p\rightarrowr)\rightarrow((q\rightarrowr)\rightarrow(p\lorq)\land\negr)\]其中的联结词运算优先级与命题逻辑合式公式完全相同。观察\(F_0\)的形式,完成以下两个题目(1)补全真值表pqr\(p\rightarrowr\)\(q\rightarrowr\)
- 2024-02-122-SAT学习笔记
2-SATk-SAT问题SAT是适定性(Satisfiability)问题的简称。一般形式为k−适定性问题,简称k−SAT。而当k>2时该问题为NP完全的。所以我们只研究k=2的情况。2−SAT,简单的说就是给出n个集合,每个集合有两个元素,已知若干个<a,b>,表示a与b矛盾(其中a与b属于不同的集合)。然后从每个集合选择
- 2024-01-14谓词在命题逻辑词中的展开方法
title:谓词在命题逻辑词中的展开方法date:2022-10-29categories:数学mathjax:truetags:-离散数学-逻辑学前言一天,数学家觉得自己已受够了数学,于是他跑到消防队去宣布他想当消防员。消防队长说:「您看上去不错,可是我得先给您一个测试。」消防队长带数学家到消防队
- 2023-12-28Verilog代码中if语句判断失效,什么原因?
一、问题描述在一个工程中,分别对应[1:0]F4_clk_cnt_pos和[1:0]F4_clk_cnt_neg计数,且计数正常,我使用if语句判断当F4_clk_cnt_pos==2'b01&&F4_clk_cnt_neg==2'b11,从而进行Sample_clk时钟的反转。具体代码如下:always@(posedgeclkornegedgen_rst)beginif(n_rst
- 2023-12-26NLP复习之向量语义
向量语义词汇语义语义概念(senseorconcept)是单词含义(wordsense)的组成部分,词原型可以是多义的。同义词是指:在某些或者全部的上下文中,单词之间有相同或近似含义可能没有完全相同含义的同义词例子!即使在很多情况下(上下文语境),单词间的含义是相同的。但仍然有可能
- 2023-12-25UCB-CS170 笔记
图论DFS记录一下一个OI中没怎么学会的知识点上图是一个DFS遍历,pre数组记录了每个节点最初被访问的时间,post数组记录了每个节点最后被访问的时间(进出栈的时间)根据两个数组,可以将所有边分为四类树边(TreeEdge):DFS树中的边后向边(BackEdge):从一个节点到其祖先的边
- 2023-11-14汇编-neg求补(改变正负号)
neg指令详细解释规则:1.negreg(对寄存器操作)2.negmem(对内存操作)作用:将目的操作数的所以数据位取反加1影响的标志:进位标志(CF),零标志(ZF),符合标志(SF),溢出标志(OF),辅助进位标志(AF),奇偶标志(PF)当操作数为0时,置CF位为0当操作数不为0时,置CF位为1.386.modelflat,stdcalloptionca
- 2023-11-092-SAT
2-SAT引子有\(2n\)种药物,分成\(n\)对,每种药物恰好属于一对。现有一种治疗方法,每一对药至少吃一种,但有某些药不可以两个一起吃,求任意一种合法的吃药方案。这样的现实问题可以转换为一个布尔方程组表示,设\(a\),\(a=1\)表示吃\(a\)种药,\(a=0\)表示不吃\(a\)种药。在大
- 2023-11-06NOIP2023模拟12联测33 总结
NOIP2023模拟12联测33总结目录NOIP2023模拟12联测33总结比赛过程正解A.构造题目大意思路思路B.游戏题目大意思路C.数数题目大意D.滈葕题目大意思路总结比赛过程先看了一眼\(T1\),发现又是恶心构造题,果断跳过。\(T2\)期望题,这么恶心吗,果断跳过。看看\(T3\)发现好像有
- 2023-11-06NOIP2023模拟12联测33
NOIP2023模拟12联测33D.滈葕目录NOIP2023模拟12联测33D.滈葕题目大意思路code题目大意思路放一段题解的材料ABO血型系统是血型系统的一种,把血液分为A,B,AB,O四种血型。血液由红细胞和血清等组成,红细胞表面有凝集原,血清内有凝集素。根据红细胞表面有无凝集原A和B
- 2023-10-20P6378 [PA2010] Riddle-2sat优化建图
P6378[PA2010]Riddle-2sat优化建图\(n\)个点\(m\)条边的无向图被分成\(k\)个部分。每个部分包含一些点。请选择一些关键点,使得每个部分恰有一个关键点,且每条边至少有一个端点是关键点。\(1\leqn,m\leq10^6\)边的限制用\(n\)个变量\(x_1\dotsx_n\),其中\(x_i\)