Questions tagged [propositional-logic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers
49 views

Is there a model for the given logical formula, and if not, why?

I'm trying to determine whether there exists a model for the following logical formula: $(p_1 \to (p_2 \lor p_3)) \land(p_2 \to \neg p_3) \land ((p_1 \lor p_3) \to \neg p_2)$. Here's my understanding ...
cozen's user avatar
  • 3
0 votes
1 answer
31 views

How big is a formula equivalent to a wff over $n$ variables with $2^n$ subformulas?

Definitions: Let $n \in \mathbb{N}$. If $\alpha$ and $\beta$ are propositional formulas, then we'll call $\alpha$ and $\beta$ independent if neither implies the other, or more formally, if $\lnot (\...
ShyPerson's user avatar
  • 923
2 votes
0 answers
19 views

Stålmarck's method, can triplets be dropped once they triggered equivalences

In Sheeran, Mary, and Gunnar Stålmarck: A tutorial on Stålmarck’s proof procedure for propositional logic there is an example application of the method to...
user3128's user avatar
0 votes
0 answers
32 views

Growth of a set of propositional formulas under partial evaluation

Definitions: Let $n \in \mathbb{N}, n \geq 1$. We write $|\alpha|$ to denote the length in characters of an expression $\alpha$ in propositional logic. We define partial evaluation in the normal way ...
ShyPerson's user avatar
  • 923
1 vote
1 answer
36 views

Complexity of a Set of Formulas

Notation: We write $|\alpha|$ to denote the length in characters of an expression $\alpha$ in propositional logic. Consider an expression $\alpha_n$ in disjunctive normal form built from $2n$ ...
ShyPerson's user avatar
  • 923
0 votes
0 answers
32 views

What are the applications of Belief Revision?

In my Computer Science graduation, I came across this concept of Belief Revision, which focus on knowledge representation and the possible operations that can be done with the facts that a "...
Jonas's user avatar
  • 103
0 votes
2 answers
43 views

Is T V F a tautology?

(Consider $T=true$, $F=false$) I apologize for the simple question but I'm confused as to what is a tautology and what isn't and I haven't found a clear definition. I think that a tautology is a ...
Ayyware's user avatar
2 votes
1 answer
25 views

Sequent calculus and vs comma: $a \land b \implies ...$ vs $a, b \implies ...$

I was reading "Open Logic book", "Sequent Calculus". Given the fact that all antecedents must hold for at least one succedent to hold, I can't get rid off the impression that using ...
dgan's user avatar
  • 123
0 votes
1 answer
51 views

Is any 2-CNF has 2-DNF representation?

I was asked a question whether I could come up with a 2-CNF over several variables that has no 2-DNF representation. However I thought that any CNF can be converted to DNF through some manipulations e....
FirePapaya's user avatar
0 votes
0 answers
59 views

Proving that the polish notation has unique readability

I am familiar with the polish notation when it comes to algorithmically reading phrases, but I am having a hard time proving the following exercise: K is a function so that 1) $K(*)$ is an integer if ...
Tita's user avatar
  • 225
1 vote
0 answers
48 views

Application of a formal definition of $max, min$ to evaluate an expression

For an Algorithms course we are studying propositional calculus. As an excercise we are given formal statements which we are to explain in natural language first and then evaluate with specific values....
lafinur's user avatar
  • 181
0 votes
1 answer
120 views

Is "Bitwise Complement Operator" (~ tilde) distributive?

To be more precise, Is ~(a+b) = ~a + ~b? Here, "~" bitwise NOT operator. I ran into this question while thinking about ...
siv2r's user avatar
  • 1
0 votes
0 answers
11 views

State of the art construction of OBDDs

I have some Boolean functions represented by pretty big Boolean formulas and I need to build OBDDs from the formulas for further manipulation. How to do it is well known with textbook algorithms but I ...
Nicola Gigante's user avatar
0 votes
2 answers
159 views

My attempt at the "This statement is false" paradox

(I haven't read any literature on this paradox nor am I good at formal proofs, so this is just my intuitive thoughts on the paradox.) If we assume the statement "This statement is false" as ...
ChocolateOverflow's user avatar
1 vote
1 answer
80 views

Proof that propositional resolution is refutation complete

I am studying theoretical computer science and I am in the part about resolution in propositional calculus. I was reading a theorem (and its proof) that propositional resolution is refutation complete,...
Gabriel F. Silva's user avatar
0 votes
1 answer
28 views

How to get the formal model using propositional logic

Input There are three chairs (1,2,3) in the same row. We need to find a seat for three guests (a,b,c). Constraints The first guest does not want to be seated next to the third one (neither left nor ...
yeahman14's user avatar
0 votes
2 answers
48 views

Logical equivalence priority

I have the logical formula $$ A \Leftrightarrow B \Leftrightarrow C $$ In order to make the truth table I'm not sure wheither I should interpret it as $A \Leftrightarrow B \Leftrightarrow C$ or $A \...
tixerauRIP's user avatar
1 vote
1 answer
65 views

Logical Consequence - Equivalent Assertions

I have the following slide in my notes and I'm having trouble understanding how the three assertions are equivalent. I understand to a degree how the 2nd and 3rd assertions are equivalent, but the ...
A. Boy's user avatar
  • 11
1 vote
1 answer
69 views

Simple Skolemization Question

Is it correct that, under a certain signature S, two First Order Logic formulae F and G are equisatisfiable if (F is satisfiable under S iff G is satisfiable under S)? But in Skolemization I’m ...
Abhishek Manikandan's user avatar
0 votes
0 answers
189 views

Horn Satisfiability is NP Complete, isn't it?

To show that any formal language is NP Complete first it must be showed that this formal language is both in NP and NP Hard. So to show that Horn Satisfiability is NP Complete first it must be showed ...
Farewell Stack Exchange's user avatar
-1 votes
2 answers
85 views

Is there a quantifier more powerful than the other to determine FOL connector?

So basically we have 2 types of quantifier in first order logic, they are universal quantifier and existential quantifier. Usually we use implies connector(->) when we have universal quantifier in ...
Thomas Iskandar's user avatar
3 votes
1 answer
69 views

Stalmarck's method: x ≡ x → z, does z have to be true?

I have been researching Ståmarck's method 1. In the paper cited here, some rules are given. Rules are made of triplets (x, y, z) such that: y $\to$ z $\equiv$ x where x, y and z are booleans which ...
Leop's user avatar
  • 53
-1 votes
1 answer
64 views

Conjuctive Normal Form

Let f(P,Q,R) be the truth-function defined as follows. f(P,Q,R)=1 if and only if Q and R have different truth-values; or P and R have the same truth-values. Choose all formulas that are in conjunctive ...
Asghar Esfahani's user avatar
0 votes
1 answer
106 views

NP-Completeness of SAT with given hamming weight k [duplicate]

I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction. Input: A propositional formula $\varphi$ and a number $k$. Output: Yes if exists an valuation $\...
ricardorr's user avatar
  • 115
0 votes
1 answer
76 views

Is it possible to encode contradictory horn clauses without goal clauses?

Intuitively, this seems impossible (because negation is forbidden in the head), but i am not sure. A naive (and wrong) example is p :- p But, this just means ...
chansey's user avatar
  • 275
-1 votes
2 answers
96 views

Proof of a logical theorem

Prove that if for every proposition $\psi\left(p_{0}, \ldots, p_{n}, p\right)$ there exists $\phi\left(p_{0}, \ldots, p_{n}\right)$ in which $\psi\left(p_{0}, \ldots, p_{n}, p\right) \rightarrow\left(\...
user260541's user avatar
0 votes
2 answers
110 views

Validity of proof by contradiction

I had a doubt in the proof by contradiction technique. Under this technique, we assume the negation of what we want to prove as true, then show that assuming so generates a contradiction. Since a ...
Kashish's user avatar
2 votes
3 answers
1k views

Why is SAT based on the CNF?

I have been reading up on Boolean logic and, specifically, the Boolean satisfiability problem. I have seen several people mention that the expression must be converted to conjunctive normal form (CNF) ...
user3670473's user avatar
1 vote
1 answer
120 views

To prove (KB ⊭ S) and (KB ⊭ ¬S) is satisfiable

In question (e), I have to prove: A ≡ (KB ⊭ S) and (KB ⊭ ¬S) is satisfiable, where KB and S are propositional variables. I am not able to follow the solution given in the image above as to why it is ...
Venky's user avatar
  • 21
4 votes
1 answer
47 views

Is there a $L$-complete variant of SAT?

Many complete problem of different class of complexity has SAT variant. Like 3-SAT or $k$-SAT is $NP$-complete, Horn-SAT is $P$-complete, 2-SAT is $NL$-complete, and so on. So I was wondering if there ...
Ozlo Rahmin's user avatar
1 vote
1 answer
98 views

Incomplete definition of function- first order logic

Let $\Sigma=\{c,f^1,R_1^2,...,R_k^2\}$ where $c$ is constant, $f$ is one argument function, and $R_i$ are binary relations. Let $\Sigma_2=\{c',g^2,R_1'^1,...,R_k'^1\}$ where $c'$ is constant, $g$ is ...
Ella's user avatar
  • 99
2 votes
2 answers
114 views

Problem with formalism in first order logic

This is a general question in first order logic. Assume I have alphabet $\Sigma$ that contains one-argument function (among other symbols). I want a new alphabet, $\Sigma'$, which is the same as the ...
Ella's user avatar
  • 99
2 votes
1 answer
82 views

equivalence of validity above different alphabet

Given the next alphabets: $\,\,\Sigma_1=\{R^2,P^1,=^2\}\,\,,\Sigma_2=\{c,f^1,=^2\}.$ Prove of Disprove: There's exists an algorithm, that given formula $A$ above $\Sigma_2$, builds formula $A'$ above ...
Ella's user avatar
  • 99
2 votes
1 answer
384 views

a conjunctive normal form that is a tautology

Are there any examples of CNF formulas that are tautologies? Such that every clause contains different variables so phrases like (a or not a) are rejected?
Prometheus's user avatar
0 votes
0 answers
47 views

Hoare Triple Logic

I'm having trouble understanding the logic behind Hoare Triples. The question asks for the missing value of the precondition {X} ...
Redone123's user avatar
1 vote
1 answer
62 views

What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator?

A multiple choice question asks this: Number of nonequivalent propositions that only consist of $P_1, P_2, P_3$ and use the $\iff$ logical operator is?$$A)7\text{ }B)8\text{ }C)1\text{ }D)16$$ I am ...
Titan's user avatar
  • 59
0 votes
1 answer
26 views

Doubt regarding the implications of a 2-SAT constraint

Consider an example 2-SAT instance with the constraint (x1​ ∨ x2)​. This CNF has these two implications: ¬x1​→x2​ and ¬x2​→x1​. "They actually mean, if x1​ is false then x2​ must be true, and if ...
ashishmax31's user avatar
1 vote
1 answer
73 views

Formal Logic - Natural deduction: Problem with assumptions about exists-negation

I'm stuck on how to progress with this proof, despite I have tried, I cannot see the next move. Given this proof without predicate: So far what I've accomplished: My idea is, as I can't see any ...
Jesús Díaz Castro's user avatar
0 votes
1 answer
376 views

Converting to CNF - Distribution

I am still trying to get my head around what is valid CNF and how distribution works, I am not even sure if the examples I have tried to convert are correct for one, but I am also unsure of the rule ...
pac234's user avatar
  • 81
1 vote
1 answer
405 views

Boolean logic: why is the "opposite" of and equal to or?

In boolean logic, why is the "opposite" of AND (&) equal to OR (|)? For example, why would ...
Aidan Yagoobi's user avatar
1 vote
2 answers
81 views

Propositional Logic: Entailment

Given the sentences, S1, S2, if S1 |= S2 then all models that satisfy S1 also satisfy S2, how is the following statement correct? A ∧ ¬A |= B How can something and ...
pac234's user avatar
  • 81
0 votes
1 answer
94 views

In propositional logic how is the negation equivalent?

I am unable to understand how the negation of a sentence into CNF actually makes sense, hopefully somebody can explain it to me in understandable terms! Given the sentence: If the battery is charged (...
pac234's user avatar
  • 81
0 votes
1 answer
105 views

Is Conjunctive Normal Form or not?

I have one formula that I do not understand why it is CNF and one that is not CNF, namely. p && !q (NOT NCF) and !!p(CNF). According to the exercise where I found these examples, 1 is not ...
mattssoncode's user avatar
1 vote
1 answer
764 views

Is it generally possible to convert CNF to Horn clauses?

My intuition is that it is not generally possible, but I cannot think of a proof.
apen's user avatar
  • 369
0 votes
0 answers
64 views

When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not

I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. ...
მამუკა ჯიბლაძე's user avatar
3 votes
1 answer
179 views

What is the purpose of learning propositional logic

I am in an AI class where we have extensively learned about propositional logic. I am wondering what the point of learning this is? Are there any uses for propositional logic? Beyond basic logic gates ...
Tyler Hilbert's user avatar
-1 votes
4 answers
599 views

Prove (p → ¬q) is equivalent to ¬(p ∧ q)

I need to prove the above sequent using natural deduction. I did the first half already i.e. I proved $(p\rightarrow\neg q)\rightarrow \neg (p \wedge q)$, but I'm stuck on where to start for the ...
Smiley's user avatar
  • 9
1 vote
1 answer
160 views

Proving the validity of a sequent using Modus Tollens

Problem: Prove $p \rightarrow (q \vee r), \neg q, \neg r \vdash \neg p$ using Modus Tollens. I need to prove the validity of the above sequent by using natural deduction. Initially, I didn't read the ...
Smiley's user avatar
  • 9
1 vote
0 answers
41 views

Computational complexity in Boolean network

An Boolean control networks can be expressed as \begin{equation} \label{ControlBN} \left\{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ {x_{...
MATH_LI's user avatar
  • 11
0 votes
0 answers
270 views

Simplify logical expression represented as binary tree

I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g. but have issues with the commutativity. Assuming the ...
twinrix's user avatar
  • 13