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

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
0
votes
0 answers

Implication and conclusion in propositional calculus

Let A and B be any propositions expressible in the propositional calculus notation. Show that A $\vdash$ B is provable by the rules of propositional calculus if and only if it is provable that $\vdash$ (A $\rightarrow$ B). In proving that if…
0
votes
1 answer

Converting from formula to clause

I'm trying to refresh myself on the subject. If φ= (L1 ∨...∨ Ln) whereL1,...,Ln are literals, then{L1, ..., Ln}is the clause associated to φ. How would I convert ¬(¬P ∨ Q) to a clause?
0
votes
1 answer

Is the " contrapositive relation" rigorously symmetric? What is rigorously the contrapositive of : ~X --> ~ Y?

Is the relation " being the contrapositive of" really symmetric? I mean : the contrapositive of X --> Y is ~Y --> ~X. If the relation " being the contrapositive of " is symmetric, then I can say that the contrapositive of : ~Y --> ~X is X --> Y.…
user654868
0
votes
1 answer

logical equivalence proof using propositional algebra

i need help to show that (p⇔r)⇒(q⇔r) is equivalent to ∼[(∼p∨r)∧(p∨ ∼r)]∨[(∼q∨r)∧(q∨ ∼r) using propositional algebra. I did it using truth tables but i am struggling with propositional algebra.
0
votes
3 answers

Is $(p \lor q) \to (\neg p \to (p \lor q))$ a tautology?

This question came up in a recent assignment. I was asked to find a logically equivalent alternative to the statement in the title from the options below. (p ∨ q) ∨ ¬p (¬p & ¬q) ∨ (p ∨ q) (p & q) ∨ (p ∨ q) (¬p & ¬q) ∨ (¬p & q) No matter how many…
0
votes
0 answers

Proving validity of this argument

p→ (q→r) q→ (p→r) ∴(p∨q) →r how do i prove the validity of this argument by using the rules of inference? please help i'm stuck there is too much possibility that i'm at a lost on how to start...
0
votes
1 answer

Why is this "proof" actually not a proof of SL's soundness?

Here, I'll consider only sentential logic as : sentential language and semantics + natural deduction rules. Alledged "proof" : (1) each rule of natural deduction is guaranteed or justified by a tautology (2) therefore if I assume A, B, C and…
user654868
0
votes
0 answers

Is it possible to represent "A implies B" , " A iff B" , " A Xor B " using a switching circuit diagram?

One commonly sees conjonction represented by 2 swiches on the same line ( " en série" as one says in French) and inclusive disjunction by 2 switches in parallel. But I've never seen the circuit that would represent implication, bi-implication or…
user655689
0
votes
2 answers

Can You help me simplify ~Q ∧ (P→Q) ∧ (R ∨ ~Q)?

can you help me solving this problem, I got stucked answering it in the beginning and hoping that you can help me with this. Thanks! ~Q ∧ (P→Q) ∧ (R ∨ ~Q)
JDA
  • 1
0
votes
1 answer

Deducing truth values from result of a Boolean operation

I have been given that the following Boolean operation results in "True" and I have been asked to either provide the truth values of $A, B, C$ or explain why it cannot be deduced. $$\left(A \rightarrow \left(B\lor C\right)\right)\land…
Paras Khosla
  • 6,481
0
votes
1 answer

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) (P ∧ Q) ⇒ (A ∨ R) In other words, we need…
0
votes
1 answer

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 $$ (p ∧ q) \to \neg r $$ And how to represent in a…
Lyhbm
  • 11
0
votes
0 answers

Logic, how to translate reverse implication with quantifier

I want to write this formula in the form of => (∃x)¬P(A,x) <= ¬(∀y)P(y,A) Will this equal ¬(∀y)P(y,A) ⇒ (∃x)¬P(A,x) or (∃x)P(y,A) ⇒ ¬(∀y)¬P(A,x) Because I know that the implication binds more than the quantifiers.
Tourna
  • 27
  • 6
0
votes
1 answer

Where can I read more about index notation in propositional calculus?

I'm working through Discrete Mathematics and its Applications, which early on delves into the following as part of a Sudoku solver: $$\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9} p(i,j,n)$$ Now I understand $\bigvee_{j=1}^{9} p(i,j,n)$…
0
votes
1 answer

Show that the boolean formulas $[(p ∧ ¬q) ∨ q] ∧ [(¬q ∧ p) ∨ r] and (p ∧ ¬q) ∨ (r ∧ q)$ are equivalent.

So far I got this: $[(p ∧ ¬q) ∨ q] ∧ [(¬q ∧ p) ∨ r]$: $p∧ T ∧ [(¬q∧p) ∨ r]$ $p∧ [(p∧¬q) ∨ r]$ $p \lor r$ $(p ∧ ¬q) ∨ (r ∧ q):$ $(p ∧ ¬q) ∨ (q ∧ r)$ $(p ∧( ¬q ∨ q)∧ r$ $p ∧ T ∧ r$ $p ∧ r$