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

Logic element to CNF

I have a big problem with a XNOR element expression. I analyzed the circuit in LOGISIM and it wrote me the minimal type of CNF which is (A + B + D)(A + B + ~C)(~B + C + ~D)(~A + C + ~D). The base XNOR expression looks like this Y = ~(A + B) XNOR…
Patrik
  • 1
0
votes
2 answers

What's the proper way to prove P$\rightarrow$Q is not tautologically equivalent to Q$\rightarrow$P

I want to rigorously show that [$(p \rightarrow q)\equiv(q \rightarrow q)$] is not true. $Let A =(p \rightarrow q), B =(q \rightarrow q)$ I tried to prove this by supposing $A$ and showing that $B$ does not follow. [$(p \rightarrow q) \rightarrow (q…
Bluebaron
  • 113
0
votes
2 answers

Convert expression to NAND/NOR only

I have to convert the following to NAND/NOR only (A $\wedge$ B) $\vee$ (A $\wedge$ C) $\vee$ (B $\wedge$ C) I understand how to do this problem if it was only (A $\wedge$ B) $\vee$ (A $\wedge$ C) but I can't seem to make a logical negation for the…
b7889
  • 1
0
votes
2 answers

Translate $\neg p \lor (p \land q)$ to English

I started to learn discrete mathematics using "Discrete mathematics and its Application" book. In this book exercises I couldn't find answer to the below question. Let $p$: I bought a lottery ticket this week. $q$: I won the million dollar…
Blasanka
  • 151
0
votes
1 answer

A question on a specific implication, given certain conditions

Is the implication $$A \implies \left(B \oplus C\right)$$ logically equivalent to $$\left(A \implies B\right) \oplus \left(A \implies C\right),$$ where $\oplus$ is the logical XOR operator, and $B$ and $C$ are mutually exclusive conditions?
0
votes
2 answers

Showing that Modus Tollens is sound

When asked to show that Modus Tollens is sound in the propositional calculus, I tried to do this by enumerating all interpretations using a truth table. However I am unsure that my deductions are correct: $\begin{array}{cc|ccc} P&Q&P\to…
0
votes
1 answer

Resolution refutation of a tautology not resolving.

I've been tasked with resolving the following statement to prove that it is valid: $(p\rightarrow q) \rightarrow ((p \lor r) \rightarrow (q \lor r))$ I convert to CNF with the following set of clauses as a result: $\{\{p, \lnot p, q, r\}, \{\lnot q,…
0
votes
3 answers

What does negation exactly imply in the following statement(s)?

The professor in my Discrete Mathematics class gave us the following example for the negation of a proposition. A: "All math majors are male" is the proposition. (negation)A: "It is not the case that all math majors are male" OR (negation)A: "There…
0
votes
1 answer

Set of formulas has no model

I need some help with the following problem. I have to show that the set of formulas $\{\phi_1,\phi_2,\phi_3,\phi_4\}$ has no model, where $$\begin{align*} \phi_1&=\forall x \forall y \forall z (Rxy \lor Ryz \lor Rxz)\;,\\ \phi_2&=\forall x \forall…
0
votes
1 answer

p,q are two propositions.It is given that, p ⇒ q is true.Consider the following conclusions,

$ \neg p\rightarrow\neg q$ is true $\neg q\rightarrow\neg p$ is true $p\rightarrow \neg p∨q$ is true Now which one is the correct? and explain this.Thanks!
0
votes
3 answers

Propositional statements dealing with "only if"

If I have the statement. "I can ride my bike only if tires aren't broken" and I have P(X) = "I can ride my bike" and I have Q(X) = "My tires are broken" Would the above statement be P -> Not(Q) Also what would the contrapositive of this be? in…
EidA5
  • 11
0
votes
1 answer

Why is $P(x)$ allowed to have other variables than $x$ free?

Using the common definition of a propositional function $P(x)$ as "a WFF which would be either true or false were it not for a variable $x$, with other variables also allowed to be free". For example, if we have a propositional function $P(x)$ with…
0
votes
1 answer

propositional calculus problem, is this right proof?

I would like to confirm my proof.
Orange
  • 29
0
votes
2 answers

Decide if $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology

How can I show that $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology? I tried to apply the implication rule $(p\Rightarrow q)\equiv (\neg p\vee q)$ but it doesn't seem to bring me anywhere.
stillenat
  • 169
0
votes
1 answer

Propositional Logic; Im lost!

The proof I have to solve is: $$\lnot Z,~ \bigg((\lnot Z \lor S) \lor T\bigg) \implies L \vdash L \lor T$$ Basically I have tried to work backwards trying to prove the contradiction of $L \lor T$ but cannot seem to find how to connect these two…