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

Help with axiom in propositional logic

I have an example in a propositional logic course I'm taking and I can't figure out how a certain axiom is/why it is applied in a certain step. This link: http://www.logicinaction.org/docs/ch2.pdf provides the chapter I'm reading. It is example 2.24…
Byebye
  • 277
0
votes
1 answer

Hilbert proof systems with hypothesis

This is my set of axioms: $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A \rightarrow \neg B)\rightarrow A)$ An I am…
0
votes
1 answer

Do Hypothetical Syllogism and Contraction Come as Sufficient for Self-Distribution?

If we have the following axioms (under detachment) 1. CCpqCCqrCpr-hypothetical syllogism 2. CCpCpqCpq-contraction 3. CpCqp-recursive variable prefixing Then we can deduce 4. CCpCqrCCpqCpr-distribution 3. and 4. suffice for The Deduction…
0
votes
1 answer

2 Distinct Bijective functions

I have that A is a set of $2k^2$ so it equals $\{2,8,18,32,50...\}$ How do you Construct two distinct bijections $f, g : \mathbb{Z}^{+} \to A$. I was able to get $f(x)=2x^2$ what would $g(x)$ be? Thank You
0
votes
1 answer

Using truth tables to determine logical equivalency

How do you use truth tables to determine whether or not the following pairs of statements are logically equivalent? i) (p ᴧ q)→r ii) p→(q→r) I'm confused on how you would do that, Thanks
0
votes
2 answers

If "If $A$, then $B$ and not $C$" is true, then is "If $A$ and $C$, then not $B$" true?

Suppose "If $A$, then $B$ and not $C$" is true. Is the following statement true? If $A$ and $C$, then not $B$. I know the answer is true but I don't know the basis behind it.
0
votes
2 answers

Propositional Logic, P or Q but not both.

If I had two propositions, P and Q, and wanted to write an expression such that either P or Q are true but not both, what would be the best notation for it?
Chillo
  • 29
0
votes
2 answers

Where do the brackets go in $p \wedge q \vee \neg p \rightarrow \neg q$?

I have been give the following question for homework: Let $p$ be the statement "She will graduate" and let $q$ be "She will find a job". Then what would be: "Either she will graduate and find a job, or, if she does not graduate, then she will…
Jeel Shah
  • 9,306
0
votes
1 answer

Are all substitution-closed sets schematic?

I assume everyone is familiar with propositional logic and its language. Let $S$ be a set of wffs of propositional logic. The set $S$ is said to be substitution-closed iff whenever $x$ is in $S$, then $f(x)$ is in $S$, where $f$ is a substitution.…
user107952
  • 20,508
0
votes
1 answer

Prove or disapprove a propositions

Let p,q and r be three propositions. Prove or disapprove $(p\to q) \land (q \iff r) \land (p \lor \lnot (\lnot q \lor \lnot r) \equiv p \land q \land r$ so, the way i do is LHS = $(\lnot p\lor q) \land (\lnot q \lor r) \land (\lnot r \lor q) \land…
LeonBrain
  • 159
  • 1
  • 6
0
votes
1 answer

Clarification about negation in propositional logic

I am a little stumped on the concept of resolution, and want to clarify that something is correct, primarily negation. if an expression in CNF is ${x = (a \lor b) \land (\lnot a \lor \lnot b)}$ It's negation should be: ${\lnot x = (\lnot a \land…
0
votes
1 answer

What do the symbols here mean?

I'm having trouble understanding what the symbols in this statement mean. This is the way to determine whether a Boolean Mealy machine is reactive if it helps to provide context, but I'm more interested in what these symbols mean in general because…
0
votes
0 answers

Should be a simple proof in propositional logic using Lemmon's book

In Lemmon's Beginning Logic, page 41 exercise 1g says to prove that from $\neg (P \cap Q)$ then $\neg P \cup \neg Q$ follows. 1 (1) $\neg (P \cap Q)$ (A) 2 (2) $\neg (\neg P \cup \neg Q)$ (A) 3 (3) $\neg P$ (A) 3 (4) $\neg P \cup \neg…
0
votes
0 answers

$a$ is not an associate of $b$ in correct math expression

Background: Definition: An element $a\in R$ is an associate of $b\in R$ provided $a=bu$ for some unit $u.$ Questions: I want to ask in math notation, to say that $a$ is not an associate of $b$ means that for every unit $u$, $a\neq bu$ Is that the…
Seth
  • 3,325
0
votes
0 answers

Doubt about contrapositive. (also about identifying conjunction).

The book 'How to Read and Do Proofs' by Daniel Solow has the following exercise: Find the contrapositive of the proposition, “If $n$ is an integer for which $n^2$ is even, then $n$ is even.” I thought the answer would be: "If $n$ is not even, $n$ is…
Boay
  • 11