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).

2
votes
0answers
21 views

How to deduce $\square p\to p$ from other modal axioms?

I'm trying to deduce the T axiom $\square p\to p$ from the B,D,5 (and also K) axioms. B: $q\to\square\diamond q$ D: $\square q\to\diamond q$ 5: $\diamond q\to \square \diamond q$ I tried to assume ...
0
votes
1answer
17 views

How to name a large number of variables in predicate logic?

What is the most common way of naming a large number of variables in predicate logic? I run out of variables pretty easy in long predicate logic sentences. The simple fact of using a lot of letters ...
0
votes
1answer
21 views

Consistency of a sentence in $S5$

True or false: if a modal sentence $\phi$ is consistent in K, then it is consistent in S5. This is equivalent to the contrapositive: if $\phi$ is not consistent in S5, then it's not consistent in K. ...
0
votes
1answer
29 views

Verify the following equivalence by writing an equivalence proof [on hold]

How do I show that: $$(p\rightarrow q)\land(p\lor q) \equiv q$$
0
votes
0answers
23 views

$\phi$ satisfiable implies $\square \phi$ satisfiable?

Below $\phi$ stands for a modal sentence. The question is to decide whether it is true that 1) if $\phi$ is satisfiable, then $\square \phi$ and $\diamond \phi$ are satisfiable, and 2) if $\phi$ is ...
1
vote
2answers
35 views

Categorical proof in natural deduction

I'm reading Fitch's book on Symbolical Logic and I don't understand how to prove, with natural deduction, that the following is a theorem without using any hypothesis. This is what is to be proven (...
3
votes
2answers
23 views

Natural deduction of (p->(p->q))->q on the hypothesis that p

I am struggling with natural deduction. I am doing the exercises in Fitch's book and now I am supposed to give an intelim proof of the theorem above (an intelim proof is one that uses only ...
0
votes
2answers
29 views

Give a categorical proof of p -> [q -> q]

I am doing Fitch's Exercises of Symbolic Logic, Chapter 1. This is the first exercise. We have so far axioms such as the distributivity axiom, the axiom of conditioned repetition, the transitivity of ...
0
votes
1answer
28 views

$\vdash\neg(\square \neg p\land p\land\diamond(p\land\square p\land \diamond p) )$

How to show that $\vdash\neg(\square \neg p\land p\land\diamond(p\land\square p\land \diamond p) )$ in the logic K? First of all, does this proof work? Assume the converse (i.e. that $\vdash\square \...
0
votes
0answers
17 views

How to simplify this formula in DNF?

Given a truth table, a formula in DNF was created, as shown below: (-p ^ -q ^ r) v (p ^ -q ^ r) v (p ^ q ^ -r) v (p ^ q ^ r) How would the simplification be represented? There are two r's, and two ...
0
votes
2answers
28 views

Boolean expression simplification - is my solution correct?

I have this boolean expression: (x′ ∧ y ∧ z′) ∨ (x′ ∧ z) ∨ (x ∧ y) and I simplified it using K-maps to this: (y ∧ z′) ∨ x Is my solution correct? Thanks!
2
votes
2answers
55 views

Modus Ponens - Implication vs Disjunction

The Modus Ponens inference rule is generally expressed as: $$ \begin{array}{rl} & P\rightarrow Q \\ & P \\ \hline \therefore & Q\end{array} $$ Is the below rule ...
1
vote
1answer
35 views

Is similar triangles have equal areas a proposition?

Suppose it is a proposition. So we have The conversion proposition is if two triangles have equal areas, then there are similar. The inversion proposition is that if two triangles are not similar, ...
0
votes
1answer
37 views

Russell's “propositional” paradox

In the Stanford Encyclopedia's page on Russell's Paradox, we get the following anecdote about an additional, lesser-known paradox from Russell: ...in Appendix B Russell also presents another ...
0
votes
1answer
18 views

Need help proving this entailment where the KB has sentences with multiple conjuncts

Show formally (using a proof rather than a Truth Table) that A follows from the given sentences shown. P ∧ Z (¬R ∧ ¬W) ∨ (¬P) (W ∧ Q) ⇒ P Q ∨ W Q ⇒ (A ∨ P) ...
1
vote
1answer
41 views

Show that $\vdash \Gamma \cup \{\psi\}$ implies $\vdash \Gamma \cup \{\psi'\}$ where $\psi'$ is $\psi$ with one of its bound variables renamed.

My textbook says that it is clear that: $\vdash \Gamma \cup \{\psi\}$ implies $\vdash \Gamma \cup \psi'$, where $\psi'$ is just $\psi$ with one of its bound variables renamed. I am trying to show ...
2
votes
1answer
30 views

How to think of formal derivation $\Gamma \vdash \phi$ in terms of trees/graphs?

According to my text, a finite set of formulas $\Gamma$ in a given language $L$ is derivable, denoted $\vdash \Gamma$, if $\Gamma$ belongs to the least collection of finite sets of formulas, denoted $...
0
votes
0answers
20 views

Propositional Logic Translation from sentence

I'm trying to translate below sentences to propositional logic but I don't know if my understanding of the main steps of translation are correct or not. I would like to ask for help to correct me. ...
0
votes
2answers
43 views

How can I convert this sentence to propositional logic (semantic and resolution)?

There were 3 people J, P, A. Only 2 people brought gifts to the party. If J brought a gift to the party, proof that P or A did not brought the gift. What I can think about this sentence is: $ J, P \...
0
votes
1answer
41 views

How can I prove $p \oplus (\lnot p \land q ) \equiv p \lor q$

Having a lot of trouble with the $q$ in $p \oplus q$ being replaced with $(\lnot p \land q)$. This is for my first unit of Discrete Mathematics, but it's a bit of a curve ball. I've been picking at ...
1
vote
1answer
24 views

How to prove that a theory T is inconsistent given its structure (propositional logic)

I am quite new to propositional logic and I am trying to prove the following: Given a theory $T$ in propositional logic that is the set of all the substitution instances of a given wff $\phi$, ...
1
vote
3answers
39 views

Tautological consequence and counterexamples

I know that in order to check if Q is a tautological consequence of P1, P2, ..., Pn I can look at the truth table. If, ...
0
votes
1answer
23 views

Can distributive law be applied into if-then and only-if statements?

Are the two statements can be logically equivalent, just like in OR, AND expressions? [(p ^ q) ↔ r] = [(p ↔ r) ^ (q ↔ r)] [(p ^ q) ⇒ r] = [(p ⇒ r) ^ (q ⇒ r)]
0
votes
1answer
31 views

How to write a formula, $S$, so that the set $P_1, \cdots, P_k$ is not consistent iff $S$ is valid?

A set of propositional formulas $P_1, \cdots, P_k$ is consistent iff there is an environment in which they are all true. Write a formula, $S$, so that the set $P_1, \cdots, P_k$ is not consistent ...
0
votes
0answers
88 views

Proof of Validity of My Polynomial Time Algorithm for $co-NP$ Complete Problem

I posted an algorithm yesterday, that purported to solve the co-NP Complete 'Boolean Tautology Problem' in polynomial time. Link to the algorithm : polynomial time algorithm In that post, I presented ...
1
vote
2answers
14 views

SAT for a formula using Tableaux Propositional Logic (precedence of operators)

My doubt is in check if the following formula $\phi$ is SAT or not using the Tableaux Method. Let me write formula: $\phi = \neg \left ( p \vee q \supset \left ( \left ( \neg p \wedge q \right ) \...
0
votes
1answer
34 views

question about laws of logical equivalence

i've this question which I have to solve using laws of logical equivalence but I can't. I've been trying to solve this since a few hours now. p ⊕ ( ¬ p ∧ q) ≡ p ∨ q I tried to solve the LHS using ...
1
vote
1answer
14 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
53 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
15 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
22 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
46 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 ...
-2
votes
0answers
145 views

Thinking of boolean variables as sets, and $\mathbf{P=NP=co-NP}$?

This is an algorithm I came up with, that seeks to solve the 'Boolean Tautology Problem'(which is co-NP complete) in polynomial time, using $3-DNF$ clauses. I am posting this algorithm here seeking ...
1
vote
1answer
38 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
56 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
32 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
41 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
47 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
11 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
43 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
32 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
45 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
28 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
46 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
50 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
47 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
62 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
95 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
73 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 ...