Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

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 ...
2
votes
2answers
48 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use |= to denote logical consequence , in the model-theory sense. Being x,y two formulas of a ...
1
vote
1answer
29 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y ...
-1
votes
0answers
13 views

proposition in mathematical logic

"We will have chicken in the dinner" -- is a proposition, because although we have to wait for the time of the dinner for the truth value of this declarative sentence; but once it is true it can't be ...
2
votes
2answers
60 views

What does it mean for a set of sentences $\mathcal{T}$ to “secure” a set of sentences $\Delta$?

I know the standard interpretation is: $\mathcal{T}$ secures $\Delta$ iff every interpretation that makes all members of $\mathcal{T}$ true makes at least one member of $\Delta$ true. ...
0
votes
1answer
30 views

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? ...
1
vote
2answers
53 views

Construct the truth table?

Any body help me .. How to solve this? (i) $(p\land q)\to (p \leftrightarrow (q \lor r))$ (ii) $(p \leftrightarrow q) \leftrightarrow ((p\land q) \lor (\neg q \land \neg p))$ (iii) ...
2
votes
1answer
62 views

How to write negation of statements? [on hold]

How to write negation of following statements in words? ...
0
votes
0answers
6 views

Marking Algorithm to prove satisfiability of Propositional Formulas

I'm looking for an example done on "Marking Algorithm" of Propositional Logic( the algorithm which is used to prove the satisfiability of propositional formulas ). I can't find any on the internet. ...
2
votes
3answers
50 views

Construct XNOR with only OR gates

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
3
votes
1answer
173 views

Using a truth table to determine if valid or invalid

I have some questions like if $P$ then $Q, P$ therefor $Q$ for example, how can you tell from writing your truth table if therefor $Q$ is valid or invalid? I mean I know its true because Modus Ponens ...
0
votes
2answers
31 views

Definition nested and unnested first order formulas

What's the definition of nested and unnested formulas in a first order language? I came across the term in a model theory book i'm reading, and I can't seem to find it defined there, or in my brief ...
2
votes
1answer
52 views

Proving the propositional tableau sound and complete

There is something fundamental that stops me from understanding the proofs for the propositional tableau. (1) soundness proves that all theorems that can be proved are valid (2) completeness proves ...
0
votes
1answer
35 views

How's my proof?

Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$. If p,q = (0,1) (p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1 (p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0 Therefore ...
3
votes
1answer
68 views

Prove if Tautology, Contradicton, or Neither. Is my proof ok?

Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither. If $p,q,r = (0,0,0)$ then $((p \Rightarrow ...
0
votes
1answer
26 views

Unique Readability Theorem proof

I really do not understand the Unique Readability Theorem proof (in Enderton's book). The proof essentially goes that we have wffs $\alpha, \beta, \gamma, \delta$, and that if we assume $(\alpha ...
0
votes
1answer
26 views

Proving ∀x (0|x ↔ x = 0) (divisor by Zero) - Euclidean Algorithm

I am trying to proof the total correction of Euclidean Algorithm, so I am up to proof one of the following properties which is divisor by Zero. Given this Axiom: ...
1
vote
1answer
37 views

Proof by induction of propositional formulas

I have two inductively defined operations: $\text{bin}$ base case: If $p$ is a propositional letter, then $\text{bin}(p) = 0$ inductive step $\text{bin}(\neg \phi) = \text{bin} (\phi)$ ...
5
votes
2answers
74 views

Is there a logical interpretation for equalizer and co-equalizer?

I know the logical equivalent to several universal constructions. For example product $\times$ is $\land$ and co-product $+$ is $\lor$. The associated arrows are projection and inclusion. The ...
-1
votes
2answers
65 views
1
vote
1answer
33 views

Why axiom with negation is required in propositional logic?

If we think a propositional logic with [], $\implies$, $\neg$, why we need axiom with negation in that propositional logic? Here axioms are (1) $[a \implies [b \implies a]]$ (2) $[[a \implies [b ...
4
votes
1answer
120 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
0
votes
1answer
52 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
1
vote
5answers
64 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
1
vote
2answers
34 views

How can I prove [P->(Q->R)] is equivalent to [(P^Q) ->R]

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
2
votes
2answers
69 views

Prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction

I am trying to prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction. Here is my attempt using JAPE application. ...
0
votes
1answer
46 views

A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
2
votes
1answer
32 views

If $\phi$ is satisfiable and $\mathscr{S}$ is countable, then the set of all models of $\phi$ has the cardinality of the continuum

I have just started reading Chang and Keisler and I'm already stuck in an exercise. Let $\mathscr{S}$ be a countable set of sentence letters (i.e. $\mathscr{S} = \{S_0, S_1, S_2, \dots\}$ or some ...
10
votes
1answer
905 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
2
votes
2answers
97 views
1
vote
3answers
56 views

Disjunctive simplification

What is this rule of inference called? $(P\wedge Q)\vee(P\wedge\neg Q)\vdash P$ My (silly) motivation is this answer.
0
votes
0answers
21 views

2 Propositional inference questions

Q1: Determine if the following argument is valid 1) ¬p → r ^ ¬s 2) t → s 3) u → ¬p 4) ¬w 5) u V w Therefore t → w Q2: Consider the following argument in ...
1
vote
2answers
82 views

How to determine whether a set of propositions is consistent?

Definition of consistency is: A set of formulas ⊆ WFF is consistent iff there is no A ∈ WFF such that Σ ⊢ A and Σ ⊢ (¬A). Say you have a set of propositions statements (i.e. $A \lor B \rightarrow C$, ...
0
votes
2answers
51 views

Convert this solution to inference notation

This is a proof for De Morgan's Law. Could you help me convert this to inference notation so I can understand the proof better? I find it hard reading this, specifically, which line each assumption ...
2
votes
1answer
35 views

Simple Propositional Logic Explaination?

In this example, the prof states that "Q->R doesn't depend on the assumption Q so he can discharge it, but without assumption Q, he couldn't have concluded with Q->R so the answer still depends on the ...
1
vote
2answers
63 views

Use of propositional logic connectives in the meta-language

I have a doubt that might seem a bit confusing so i will try to explain it the clearer i can. Suppose we have an expression "A o B" in the meta-language, where 'o' refers to those logical ...
1
vote
1answer
54 views

Answering questions with truth tables

"With every dinner I have three rules": If I don't drink wine, then I eat soup If I eat soup and drink wine, then I'll have some pudding If I have pudding or don't drink wine, then I'll skip the ...
2
votes
1answer
59 views

Trouble understanding Lindenbaum's lemma's proof

I'm stuck on the section (b) of the proof of the Lindenbaum's lemma in Geoffrey Hunter's Metalogic (part 32.12). Can't these two derivations ($\Gamma ' \vdash_{PS} A $ and $\Gamma ' \vdash _{PS}\sim A ...
1
vote
1answer
42 views

Help solving a challenge - relational algebra or second order logic

I am a self-taught man and I'm posting my first question here. I'm facing a challenge I'd like to solve. Based on what I know it fits propositional calculus (hope it is). Suppose 3 people: a ...
1
vote
1answer
24 views

semantic equivalence

Hi I am looking to prove that this equivalence holds using rules of semantic equivalence, or if it does not hold give an interpretation that shows it. (p⇒q)∨(r⇒q)≡p⇒(r⇒q) I get ≡implication ...
1
vote
2answers
45 views

prove formulae using natural deduction

Hello I am trying to prove this: ⊢p⇒p∧(p∨q) using natural deduction. p ⊢ p∧(p∨q) p, assumption p ⊢ (p∨q) p, assumption but dont seem to be getting anywhere. can someone please help? thank you. ...
2
votes
1answer
38 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
2
votes
5answers
134 views

truth tables and validity of arguments

$ p $ $ p \to q $ $ \lnot q \lor r$ $ \therefore r$ In order to prove validity with truth tables, do 1) 2) and 3) have to be true in order for the conclusion to be true?
1
vote
1answer
28 views

Is my answer correct for this Logical Analysis of Arguments?

The question is: If U is a subspace of V, then U is a subset of V, U contains the zero vector, and U is closed under addition. U is a subset of V, and if U is closed under addition then U contains ...
1
vote
2answers
23 views

question about equivalence of boolean statements

Does the function $(p \land q) \lor r$ equal the function $p \land (q \lor r)$? please it would be suitable if in your feedback you will include which algebraic rule for boolean function to follow.. ...
6
votes
5answers
181 views

The deep structure of logical formulas

A long-standing question to which I never found a concise answer is: Is there something like an unambiguous deep structure of a formula of propositional logic, opposed to its comparingly ...
0
votes
1answer
96 views

Propositional calculus proof must involve instance of $(\neg \neg p \Rightarrow p )$

Hi this is a question about propositional calculus. The axioms I am working with are: $(p \Rightarrow (q\Rightarrow p))$ $ ((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q ) ...
0
votes
0answers
15 views

Translate n xor expressions to CNF?

I have n xor expressions: a xor b xor c xor d... I want to translate to cnf: The answer of cnf can be found here: http://www.wolframalpha.com/input/?i=a++XOR+b++XOR+c+XOR+d+ I want to write a ...
4
votes
4answers
257 views

Derive by modus ponens $[A\rightarrow(B\rightarrow C)]\rightarrow[(A\rightarrow B)\rightarrow(A\rightarrow C)]$

How could I derive by modus ponens the formula $$[A\rightarrow(B\rightarrow C)]\rightarrow[(A\rightarrow B)\rightarrow(A\rightarrow C)]$$ from, and just from, the following axiom schemata? $(A\lor ...
1
vote
1answer
42 views

p xor q xor r — simplifying into disjunctive normal form with propositional algebra

So, I have $p \oplus q \oplus r$, and my goal is to simplify into disjunctive normal form with propositional algebra. Step 1: simplyify xor ((($p \wedge \neg q) \vee (\neg p \wedge q)) \wedge \neg ...