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
-1
votes
1 answer

Where to start when converting a logical formula to English?

I've got this problem with some atomic sentences, I was just wondering whether when converting it into English I needed to do the brackets first along with precedence or whether I just work my way along left to right. $$X \implies (X \land Y) \land…
-1
votes
1 answer

Is the contrapositive to the following statement of an exercise in hungerford correct?

Background: Exercise 5: If $a=bc$ with $a\neq 0$ and $b$ and $c$ nonunits, show that $a$ is not an associate of $b$ Questions: For the above question, is the contrapositive of the statement of the above exercise: if $a$ is an associate of $b$, and…
Seth
  • 3,325
-1
votes
2 answers

Propositional Logic: ¬p → ¬q, q V ¬r ⊢ r → p

Is this proof correct? ¬p → ¬q, q V ¬r ⊢ r → p 1. ¬p → ¬q P 2. q V ¬r P 3. r A 4. q A 5. ¬p A 6. ¬q E→(1,5) 7. p …
jcemp
  • 11
-1
votes
3 answers

the negation of $A \veebar B \veebar C $??

I need to know the negation of $A \veebar B \veebar C $, with $\veebar$ thanks in advance!!
mle
  • 2,287
-1
votes
1 answer

Need to use deduction to show $(p \lor q) \land (\lnot q \lor r) \implies (p \lor r)$ is a tautology

$$(p \lor q) \land (\lnot q \lor r) \implies (p \lor r)$$ My work so far: I feel like I'm doing something very wrong and making the problem get extremely tangled
-1
votes
1 answer

Show that $(P\land\lnot Q)\lor(\lnot P \land Q)$ is equivalent to $(\lnot(P \land Q))\land(P \lor Q)$ without using truth tables

I'm trying to show that $$(P\wedge \lnot Q)\vee(\lnot P\wedge Q) \equiv (\lnot(P \wedge Q)) \wedge (P\vee Q)$$ without using truth tables. I've been trying to expand either side through distribution and De Morgan's but I'm getting stuck with how to…
user905907
-1
votes
1 answer

Contrapositive of: If $a$ is a real number such that $|a| < r$ for every positive real number $r$, then $a=0.$

I wish to state the contrapositive of: If $a$ is a real number such that $|a| < r$ for every positive real number $r$, then $a=0.$ First, I want to state the original statement symbolically. $\exists a \in \mathbb{R} (\forall r \in \mathbb{R}^+…
-1
votes
1 answer

I am studying connectives. Please help me answer the following question.

The question below consists of a main statement followed by four options. From the options, select the one that logically follows the main statement. Statement: Either I give up or I work hard. (A) I am not going to give up, hence I will work…
-1
votes
1 answer

Logic - Simplify a propositional logic expression

any help on simplifying the following propositional expression? ¬[¬( ∧ ) ∨ (¬ ∧ )] ∧ ( ∨ ) I have done some progress but the exercise demands only one logical operator left at the end.
atom
  • 1
-1
votes
1 answer

Proving a tautology by applying a chain of logical identities

I need help showing that $[ (p \land q) \Rightarrow (p \Rightarrow q) ]$ is a tautology by applying a chain of logical identities. The question also asks to identify each identity I use. I have no clue where to start.
-1
votes
2 answers

Establish the validity by means of a truth table

The following argument is valid, establish the validity by means of a truth table. Determine which rows of the table are crucial for assessing the validity of the argument. $[p \wedge (p \rightarrow q) \wedge r] \rightarrow [(p \vee q)…
-1
votes
1 answer

5 Lined Rules of Inference Question

Use the rules of inference together with basic logical equivalences to show that the following argument is valid. Name the rule you use at each step. w ∨ ¬z → r s ∨ ¬w ¬t z → t ¬z ∧ r → ¬s —————– ∴ ¬w I'm really not sure how to work through this…
-1
votes
1 answer

Simplify the following expression. ¬[u ∨ (u ∧ r)] → ¬(r ∧ r)

so far I got: ¬[¬u ∨ (u ∧ r)] V ¬(r ∧ r)
-1
votes
1 answer

If Φ⊢¬(ϕ→ψ) , show that Φ,¬ϕ and Φ, ψ are both inconsistent.

So far I have shown that Φ, ψ is inconsistent: If Φ⊢¬(ϕ→ψ) then Φ, ψ⊢¬(ϕ→ψ) By the axiom ψ→ϕ→ψ and Modus Ponens, Φ, ψ⊢ϕ→ψ. So Φ, ψ is inconsistent. Could anyone help me to prove that Φ,¬ϕ is inconsistent?
mdryizk
  • 57
-1
votes
1 answer

I'm unable to convert this equation to NAND only.

I've been trying to convert this equation $$ S_1\cdot S_3+\bar{A} $$ to NAND only but everytime i do it i get a different result, i will be glad if someone showed me the right way to properly solve this! Thanks!