Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

1
vote
1answer
16 views

How would you use predicate logic to check if a statement is true or false?

Let $P(x,y,z)$ be the predicate $x+y<z$. Over which set is the statement $∀z∃x∃y\ P(x,y,z)$ true? $\Bbb Z^+=\{1,2,3,\dots\}$ or $\Bbb Z$? I had thought that it would be neither, but that ...
0
votes
2answers
60 views

What does the negated double turnstile ($\not\models$) mean?

I understand that the expression $\models \phi \rightarrow \psi$ means that $\phi \rightarrow \psi$ is a tautology. But what does the expression $\not\models \phi \rightarrow \psi$ mean? Does it mean ...
0
votes
0answers
17 views

Propositional Logic - Logical Simplification

Can we further simplify this statement. $\text{~a $\rightarrow$ (b $\oplus$ c)}$ I got around here and stuck. $\text{~a $\rightarrow$ ~[(b $\rightarrow$ c) $\land$ (c $\rightarrow$ b)]}$ $\text{~a $\...
0
votes
1answer
25 views

About provability of modal axioms in modal logics

Suppose I'm asked to prove that one specific axiom from the list T, 4, B, D, 5 is not provable in some modal logic (KT, K4, KB, KD, K5, S4, S5, etc.). To be specific, suppose I'm asked to prove that 4 ...
0
votes
1answer
50 views

Proving that a sentence is inconsistent [duplicate]

I'm trying to understand if the sentence $\square\bot\land \phi$ is consistent in KD. I don't think it is true because it looks like no serial model where this sentence is satisfiable exists. As I ...
1
vote
1answer
44 views

Proving $\neg (p\land \diamond q)$

Assume the Necessitation Rule and the Distribution Axiom (https://en.wikipedia.org/wiki/Modal_logic#Axiomatic_systems) of modal logic, and also assume the axiom $p\land \diamond q\to \diamond(q\land\...
2
votes
1answer
61 views

Showing $\vdash \phi\to \square \diamond \phi$

I'm trying to prove the converse of what was shown here. Namely, I'm trying to prove B-axioms of modal logic ($\vdash \phi\to \square \diamond \phi$ or $\vdash\diamond\square\phi\to\phi$, whatever is ...
1
vote
1answer
34 views

$\vdash\phi \land \diamond\psi \to \diamond(\psi\land\diamond\phi)$ in KB

I've been trying to prove $\vdash\phi \land \diamond\psi \to \diamond(\psi\land\diamond \phi)$ in natural deduction where it's allowed to use $\phi\to \square \diamond \phi$ and/or $\diamond\square\...
1
vote
1answer
48 views

Prove $\vdash \neg(\square F\land p)$ in $KD$

How to prove that $\vdash \neg(\square F\land p)$ in $KD$? The allowed rules are natural deduction rules and the axiom $\square p\to\diamond p$ where $\diamond p=\neg\square\neg p$. I actually don't ...
0
votes
0answers
49 views

Intuitionist Logic Question [duplicate]

Show that it is not the case that if ⊨ ¬(A ∧ B) then ⊨ ¬A or ⊨ ¬B. Consider the formula ¬(p∧¬p). Replace A with p and B with ¬p. Validity: this is defined as truth preservation over all worlds of ...
0
votes
0answers
20 views

Is it possible to prove that propositional calculus is consistent using only its syntax?

Let us consider Gentzen's propositional calculus with only one axiom: $$ \phi \vdash \phi $$ and 12 rules of inference. As far as I know this PC is consistent, i.e. not all of their expressions (...
0
votes
3answers
44 views

General rule for $(A \land B) \lor (\neg A \land D)$

I encountered the following small expression: $$ (n\ge0\land y \gt 5) \lor(n \lt 0 \land x > 10). $$ The answer should be easily $(x > 10 \land y \gt 5)$ but unfortunately I don't see how ...
1
vote
1answer
33 views

Minimize term without Karnaugh map

I have the following term, that should get minimized with Boolean algebra (no Karnaugh map!): (a ∧ ¬b ∧ c) ∨ (a ∧ c ∧ d) ∨ (b ∧ d) I already figured out, that the minimzed term is as follows (...
1
vote
2answers
51 views

Propositional logic meets diplomacy at the workplace

This is just a funny little incident that made me think. Please don't take it too seriously or the wrong way. I would still like to hear your opinion on it, though. I wrote an email to a colleague ...
0
votes
0answers
30 views

meaning of $←$ in propositional logic

what is the meaning of the symbol ($←$) in regards to boolean logic? Here is an example of the notation I have come across while reading about qualitative choice logic theory $$T = \{w\land s > \...
0
votes
1answer
52 views

Boolean Expression Simplification Problem

I started with a big problem and through various simplifications I've arrived at a point where I don't quite know what else to do. I've tried to further simplify but I keep running into issues. ...
0
votes
2answers
73 views

Complexity of a recursive algorithm on formulas of propositional logic

A proof I've seen on reductions for $\mathsf{NP}$-hard problems relies on evaluating the complexity of an algorithm computing a function which is defined recursively in the structure of formulas of ...
2
votes
1answer
57 views

Why is the right implication rule of multi-succedent intuitionistic sequent calculus (LJm) not invertible?

On page 57 of A Short Introduction to Intuitionistic Logic (Mints), the author provides an exercise: prove that the right implication rule is not invertible. By an invertible rule he means: if the ...
2
votes
1answer
152 views

Tseytin transformation example

I am trying to understand Tseytin transformation and I can't really find any reliable info on the internet. I pretty much understand the steps until I get to the point I have to convert all ...
1
vote
0answers
39 views

why does a closed circuit represent a false proposition? (Claude Shannon thesis)

In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits. As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
2
votes
0answers
98 views

How many distinct subsets of binary boolean operators are closed under composition?

Question: There are $2^4=16$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $...
1
vote
2answers
76 views

Backward entailment

An valid argument (p⊩c) is one where the premises (p) necessarily lead to the conclusion (c) , with truth table one check its validity by showing that p⟹c is a tautology ( ⊩p⟹c ) .in such manner we ...
6
votes
2answers
73 views

Is $P(tautology) = 1$? What are the connections between logic and probability?

It's well-known that sets are "isomorphic" to logic: if we treat $\varphi(A_1, A_2)$ as a shorthand for $\forall x: \varphi(x \in A_1, x \in A_2)$ then $A \land B \equiv A \cap B$ and $A \rightarrow B ...
1
vote
1answer
30 views

A question about being correctly decidable

I feel like a bit of an idiot, but I can't figure this question out: Suppose any sentences $X$ and $Y$ are correctly decidable in any arbitrary system $S$, then $X \rightarrow Y$ is also correctly ...
0
votes
0answers
31 views

Is there utility in a boolean function that flags the set of integers?

I'm working on a math that might allow defining a differentiable function using elementary expressions which yields a 1 if a real number is an integer, and a 0 otherwise. I'm just curious if there ...
3
votes
1answer
98 views

Compactness and the canonical model in modal logic

For simplicity, consider the modal logic $\mathsf{K}$, i.e. propositional calculus extended by the scheme $$\Box(\phi\rightarrow\psi)\rightarrow(\Box\phi\rightarrow\Box\psi)$$ and the necessitation ...
0
votes
1answer
54 views

Difference between ⊢ as connective versus in front

What is the meaning of ⊢ in the context of ⊢(P->Q) versus in the context of (P ⊢ Q)
0
votes
3answers
40 views

a problem in justifying ONLY IF truth table

EDITED:I saw the link above but it does't answer my question.I have a clear understanding of "P ONLY IF Q", I know that it equals "IF P THEN Q" .. but I see that there is a difference in the case ...
1
vote
1answer
41 views

Why is propositional logic often considered just a “toy”?

I recently posted a question on the relation between triviality and decidability in a logic. As a footnote to that post, I added that propositional logic is often considered just a "toy". The ...
2
votes
1answer
61 views

Why a decidable logic is considered trivial?

I was reading some notes on propositional logic and I stumbled upon these related remarks: "One way of measuring the strength of a logic is to ask whether it is decidable" "One of the things ...
3
votes
1answer
57 views

Don't the natural deduction inference rules assume semantics?

I read that one should separate syntax snd semantics in logic but then how come we have things like this: $a \land b \vdash a$ $a \land b \vdash b$ Which says "If we know $a \land b$ then we also ...
1
vote
2answers
54 views

tautology vs axiom vs premise

I am trying to sharpen the line among the definitions of tautology, axiom and premise. What I have understood so far is this: Tautology: A statement that is proven to be true without relying on any ...
1
vote
1answer
48 views

Example of a complete and consistent set of formulas in propositional logic

So, I am aware that every set which is inconsistent is complete (every formula can be derived from it) and that a set is consistent if and only if it is satisfiable. But what is an example of ...
1
vote
2answers
58 views

Truth sets and set diagrams

I am confused on how to produce truth sets from propositional logic statements For example: $(p \land q) \implies \lnot r$ How would I turn this into a truth set, which could then be used to create ...
1
vote
1answer
27 views

Boolean Expression Simplification - Issue

I don't understand where to even begin with this problem. Any helpful tips would be nice. $(A \lor \lnot B \lor \lnot D) \land (\lnot B \lor C \lor D) \land (B \lor \lnot C \lor \lnot D)$
0
votes
1answer
59 views

Truth set of (p ∧ q) → ¬r and venn diagram of this?

Venn Diagram Image I am struggling to understand truth sets and the symbols used. In this context $P, Q, R$ are truth sets of $p,q,r$. I am unsure of how to find the truth set of this expression $$ ...
1
vote
3answers
94 views

How can $P \lor Q,~ P \vdash \lnot Q$ be invalid?

While studying refutation tree and I came across this example: $P \lor Q,~ P \vdash \lnot Q$ in Outline of Logic- Schaum's series. The solution invalidates the argument. But, when we cross ...
0
votes
1answer
30 views

Distributive laws and Absorption laws with negation

I'm currently stumped because I can't seem to find a way though this proof I'm currently doing. I did notice because of this proof that I'm really not sure how to handle these two situations... 1) A ...
1
vote
1answer
37 views

Complementing function using DeMorgan's Laws

The question states find the complement of the following expression: x'y' + xy i am not sure about my solution which is: (x'+y') + xy
2
votes
1answer
38 views

Boolean expression simplification using 3 variables

(!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(1) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(C + !C) = (!A B !C) + (B !C !D) + (!ACD) + (...
1
vote
2answers
30 views

Boolean expression simplification - Short problem

I don't know exactly how to simply this problem. I can clearly see that (A + B) is in all of them but I don't know what to do next. (A + B + C)(A + B + !C + D)(A + B + !C + !D) -- Edit 1 -- I am ...
0
votes
2answers
47 views

Quantifier Positioning

How does the positioning of a quantifier affect the meaning of the statement? For example, what is the difference between $\forall x : \forall y : (P(x) \land P(y))$ and $(\forall x: P(x)) \land (\...
0
votes
0answers
15 views

How to prove for all $n \in \mathbb{N}$, there is a circuit of depth $2$

The depth of a circuit is the maximum number of gates a wire in a logic circuit travels from input to output. I want to show that for all $n \geq 1$, there is a circuit with depth $2$ satisfying $f_{...
0
votes
1answer
58 views

How to solve this logic exercise?

It turns out that there is a determined exercise that I was looking at, but I do not understand how it reaches the following conclusion: 1) $P \Rightarrow \neg [ (\neg P \Rightarrow Q) \land \neg(\...
1
vote
1answer
88 views

Inversion lemma proof

I am following Structural Proof Theory by Negri and others, and I don't understand the Inversion Lemma proof (i) (the system is G3$_{ip}$, which is the same as G3$_i$ only that it excludes quantifier ...
3
votes
0answers
55 views

What will be the notion of a “valid deduction” in the following system?

Consider the Propositional Calculus whose axiom schemes and rule of inference are given below (here $P,Q$ and $S$ are formula schemes, $\color{crimson}{\text{Axiom 1.}}\ P\to (Q\to P)$ $\...
5
votes
3answers
148 views

Need help formalising simple propositional logic sentences

I'm a beginner learning about propositional logic and how to formalise sentences. I'm currently working through the following sentences and translating them into logical statements. $p$ means “...
1
vote
1answer
48 views

Find the simplest proposition logically equivalent to $(p \Rightarrow q) \Rightarrow ( p \Leftrightarrow q)$

Here is what I've gotten so far ... $$ (p\Rightarrow q) \Rightarrow ( p \Leftrightarrow q)$$ $$\Leftrightarrow (\lnot p \vee q) \Rightarrow ((p\Rightarrow q) \wedge (q\Rightarrow p))$$ $$\...
0
votes
2answers
130 views

How the logical form “ P implies Q” differ from “P does not implies Q ”?

i have recently seen a question that is stated as " p does not implies q " but due to confusion i have seen a similar question on stack exchange but there is a problem on stack exchange which i do ...
0
votes
1answer
12 views

Prove the following implications, and for each draw Venn diagram.

In what follows X is a set, A, B, C, etc., are subsets of X. The complement of a subset Y ⊂ X is denoted $Y^c$ . Prove the following implications, and for each draw Venn diagram. 1) A ⊆ B ⇒ A ⊆ (B ∪ ...