// Numbas version: exam_results_page_options {"showstudentname": true, "metadata": {"licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International", "description": "

A collection of questions (frequently updated) to demonstrate the usage of the Logic extension.

\n

Current questions:

\n
\n
• Make syllogisms (either valid, invalid or valid under an additional assumption);
• \n
• Write statements in Polish and reverse Polish notation, find the truth table, determine satisfiability;
• \n
• Test whether a collection of statements $\\Gamma$ models a statement $\\phi$;
• \n
• Write the Disjunctive and Conjunctive Normal Forms for a statement.
• \n
\n

Needs the Logic Extension!

"}, "question_groups": [{"pickQuestions": 1, "name": "Group", "pickingStrategy": "all-ordered", "questions": [{"name": "Syllogisms", "extensions": ["Logic"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "contributors": [{"name": "Andrew Iskauskas", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/724/"}], "statement": "

For the following syllogisms, determine whether they are valid, invalid, or valid under an additional assumption.

\n

Note that a premise may, on its own, be incorrect! However, you should assume that the two premises are true to determine the validity of the syllogism.

", "ungrouped_variables": ["marking_matrix", "checkforcoverage"], "metadata": {"description": "

A syllogism generator. For some sets of three categories, it generates syllogisms that can be either valid, invalid, or valid under an assumption of existence.

\n

Uses the \"Logic\" extension: for details see the documentation.

", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "variables": {"true2": {"definition": "random([true,false])", "description": "

Determines whether the syllogism is to be true. This, along with exist2, motivates the choice of syllogism.

", "name": "true2", "templateType": "anything", "group": "Set 2"}, "fig3": {"definition": "random(1..4)", "description": "

Selects the 'figure type'. If a statement has a middle M, subject S, and predicate P, then the figures have major and minor premise

\n

Figure 1: M-P; S-M

\n

Figure 2: P-M; S-M

\n

Figure 3: M-P; M-S;

\n

Figure 4: P-M; M-S.

\n

All figures end with the conclusion S-P.

", "name": "fig3", "templateType": "anything", "group": "Set 3"}, "exist5": {"definition": "random([true,false])", "description": "

Determines whether (if the syllogism is true), it is only true under an additional existential assumption.

", "name": "exist5", "templateType": "anything", "group": "Set 5"}, "set4": {"definition": "[\"X\",\"Z\",\"Y\"]", "description": "

List of three (potentially connected) items.

", "name": "set4", "templateType": "anything", "group": "Set 4"}, "set2": {"definition": "[\"Martian\",\"human\",\"alien\"]", "description": "

List of three (potentially connected) items.

", "name": "set2", "templateType": "anything", "group": "Set 2"}, "true4": {"definition": "random([true,false])", "description": "

Determines whether the syllogism is to be true. This, along with exist4, motivates the choice of syllogism.

", "name": "true4", "templateType": "anything", "group": "Set 4"}, "fig2": {"definition": "random(1..4)", "description": "

Selects the 'figure type'. If a statement has a middle M, subject S, and predicate P, then the figures have major and minor premise

\n

Figure 1: M-P; S-M

\n

Figure 2: P-M; S-M

\n

Figure 3: M-P; M-S;

\n

Figure 4: P-M; M-S.

\n

All figures end with the conclusion S-P.

", "name": "fig2", "templateType": "anything", "group": "Set 2"}, "fig5": {"definition": "random(1..4)", "description": "", "name": "fig5", "templateType": "anything", "group": "Set 5"}, "set3": {"definition": "[\"cat\",\"animal\",\"mammal\"]", "description": "

List of three (potentially connected) items.

", "name": "set3", "templateType": "anything", "group": "Set 3"}, "exist2": {"definition": "random([true,false] except exist1)", "description": "

Determines whether (if the syllogism is true), it is only true under an additional existential assumption.

", "name": "exist2", "templateType": "anything", "group": "Set 2"}, "fig1": {"definition": "random(1..4)", "description": "

Selects the 'figure type'. If a statement has a middle M, subject S, and predicate P, then the figures have major and minor premise

\n

Figure 1: M-P; S-M

\n

Figure 2: P-M; S-M

\n

Figure 3: M-P; M-S;

\n

Figure 4: P-M; M-S.

\n

All figures end with the conclusion S-P.

", "name": "fig1", "templateType": "anything", "group": "Set 1"}, "set5": {"definition": "[\"Engineer\",\"Mathematician\",\"Physicist\"]", "description": "

List of three (potentially connected) items.

", "name": "set5", "templateType": "anything", "group": "Set 5"}, "exist1": {"definition": "random([true,false])", "description": "

Determines whether (if the syllogism is true), it is only true under an additional existential assumption.

", "name": "exist1", "templateType": "anything", "group": "Set 1"}, "fig6": {"definition": "random(1..4)", "description": "", "name": "fig6", "templateType": "anything", "group": "Set 6"}, "true5": {"definition": "random([true,false])", "description": "

Determines whether the syllogism is to be true. This, along with exist5, motivates the choice of syllogism.

", "name": "true5", "templateType": "anything", "group": "Set 5"}, "fig4": {"definition": "random(1..4)", "description": "

Selects the 'figure type'. If a statement has a middle M, subject S, and predicate P, then the figures have major and minor premise

\n

Figure 1: M-P; S-M

\n

Figure 2: P-M; S-M

\n

Figure 3: M-P; M-S;

\n

Figure 4: P-M; M-S.

\n

All figures end with the conclusion S-P.

", "name": "fig4", "templateType": "anything", "group": "Set 4"}, "exist4": {"definition": "random([true,false] except exist3)", "description": "

Determines whether (if the syllogism is true), it is only true under an additional existential assumption.

", "name": "exist4", "templateType": "anything", "group": "Set 4"}, "true1": {"definition": "random([true,false])", "description": "

Determines whether the syllogism is to be true. This, along with exist1, motivates the choice of syllogism.

", "name": "true1", "templateType": "anything", "group": "Set 1"}, "checkforcoverage": {"definition": "oneofeach([[true1,exist1],[true2,exist2],[true3,exist3],[true4,exist4],[true5,exist5],[true6,exist6]])", "description": "

Makes sure that the results contains at least one of \"True\", \"False\", and \"True under an additional assumption\". Script for oneofeach is in 'extensions and scripts'.

", "name": "checkforcoverage", "templateType": "anything", "group": "Ungrouped variables"}, "set1": {"definition": "[\"grommet\",\"widget\",\"gadget\"]", "description": "

List of three (potentially connected) items.

", "name": "set1", "templateType": "anything", "group": "Set 1"}, "set6": {"definition": "[\"elf\",\"orc\",\"wizard\"]", "description": "

List of three (potentially connected) items.

", "name": "set6", "templateType": "anything", "group": "Set 6"}, "exist6": {"definition": "random([true,false])", "description": "

Determines whether (if the syllogism is true), it is only true under an additional existential assumption.

", "name": "exist6", "templateType": "anything", "group": "Set 6"}, "true6": {"definition": "random([true,false])", "description": "

Determines whether the syllogism is to be true. This, along with exist6, motivates the choice of syllogism.

", "name": "true6", "templateType": "anything", "group": "Set 6"}, "exist3": {"definition": "random([true,false])", "description": "

Determines whether (if the syllogism is true), it is only true under an additional existential assumption.

", "name": "exist3", "templateType": "anything", "group": "Set 3"}, "true3": {"definition": "random([true,false])", "description": "

Determines whether the syllogism is to be true. This, along with exist3, motivates the choice of syllogism.

", "name": "true3", "templateType": "anything", "group": "Set 3"}, "marking_matrix": {"definition": "matrix([if(true1, if(exist1, [0,0,1], [1,0,0]), [0,1,0]),\n if(true2, if(exist2, [0,0,1], [1,0,0]), [0,1,0]),\n if(true3, if(exist3, [0,0,1], [1,0,0]), [0,1,0]),\n if(true4, if(exist4, [0,0,1], [1,0,0]), [0,1,0]),\n if(true5, if(exist5, [0,0,1], [1,0,0]), [0,1,0]),\n if(true6, if(exist6, [0,0,1], [1,0,0]), [0,1,0])])", "description": "

Marking matrix formed from the results of true1-6 and exist1-6.

", "name": "marking_matrix", "templateType": "anything", "group": "Ungrouped variables"}}, "functions": {"oneofeach": {"parameters": [["arr", "list"]], "definition": "// Simple check that a set contains each of [0,i], [1,0], [1,1] (i can be 0 or 1).\nvar sometrue = false, somefalse = false, someexist = false;\nfor (i=0; iWe can break down any syllogism into a predicate, subject and middle: the conclusion relates the subject and the predicate. The ordering of subject, middle and predicate in the major and minor premises, and the use of \"all are...\", \"all are not...\", \"some are...\" and \"some are not...\" determines the validity.

\n

Consider the following syllogisms

\n\n\n\n\n\n\n\n\n
 \nAll mammals are animals;\nAll cats are mammals;\nTherefore all cats are animals.\n \nSome mammal is an animal;\nAll cats are mammals;\nTherefore some cats are mammals.\n \nAll mammals are animals;\nAll cats are mammals;\nTherefore some cat is an animal.\n
\n

Let's denote by $M$, $A$ and $C$ the sets of mammals, animals and cats, respectively.

\n

The first syllogism is valid: we can see this through transitivity of equivalence: $M=C=A$. (Note that even if every set is empty, the equivalence still holds: we will see the importance of that shortly)

\n

The second syllogism is not valid: it is not necessarily true that the shared set $C \\cup M \\cup A$ is non-empty. $C$ is a subset of $M$, and some elements of $M$ must be in $A$, but those elements needn't be contained in $C$.

\n

The final syllogism is valid, but only if we assume the existence of cats (i.e. assume the set $C$ is non-empty). If a cat exists, then it must be an animal and therefore the syllogism holds; if no cat exists, then the conclusion (a particular cat is an animal) does not hold.

", "variable_groups": [{"variables": ["set1", "fig1", "true1", "exist1"], "name": "Set 1"}, {"variables": ["set2", "fig2", "true2", "exist2"], "name": "Set 2"}, {"variables": ["set3", "fig3", "true3", "exist3"], "name": "Set 3"}, {"variables": ["set4", "fig4", "true4", "exist4"], "name": "Set 4"}, {"variables": ["set5", "fig5", "true5", "exist5"], "name": "Set 5"}, {"variables": ["set6", "fig6", "true6", "exist6"], "name": "Set 6"}], "parts": [{"unitTests": [], "warningType": "none", "answers": ["

Valid

", "

Invalid

", "

"], "extendBaseMarkingAlgorithm": true, "marks": 0, "variableReplacementStrategy": "originalfirst", "minMarks": 0, "showCorrectAnswer": true, "shuffleChoices": true, "showFeedbackIcon": true, "displayType": "radiogroup", "scripts": {}, "layout": {"expression": "", "type": "all"}, "customMarkingAlgorithm": "", "choices": ["

{syllogism({set1},{fig1},{true1},{exist1})}

", "

{syllogism({set2},{fig2},{true2},{exist2})}

", "

{syllogism({set3},{fig3},{true3},{exist3})}

", "

{syllogism({set4},{fig4},{true4},{exist4})}

", "

{syllogism({set5},{fig5},{true5},{exist5})}

", "

{syllogism({set6},{fig6},{true6},{exist6})}

"], "variableReplacements": [], "type": "m_n_x", "maxMarks": "6", "matrix": "marking_matrix", "minAnswers": 0, "maxAnswers": 0, "shuffleAnswers": false}], "variablesTest": {"condition": "checkforcoverage", "maxRuns": "200"}, "tags": [], "rulesets": {}, "type": "question"}, {"name": "Logical Statements and Truth Tables", "extensions": ["Logic"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "contributors": [{"name": "Andrew Iskauskas", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/724/"}], "rulesets": {}, "tags": [], "ungrouped_variables": [], "variablesTest": {"condition": "", "maxRuns": 100}, "preamble": {"js": "", "css": ""}, "variable_groups": [{"variables": ["noofvbls", "components", "prefix", "infix", "postfix", "truth_table", "answer_output", "taut"], "name": "Statements and Truth Tables"}], "parts": [{"unitTests": [], "variableReplacements": [], "marks": 0, "variableReplacementStrategy": "originalfirst", "scripts": {}, "customMarkingAlgorithm": "", "prompt": "

Write the statement in Polish notation.

\n

[[0]]

", "showFeedbackIcon": true, "showCorrectAnswer": true, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "gaps": [{"unitTests": [], "variableReplacements": [], "marks": "2", "displayAnswer": "{prefix}", "variableReplacementStrategy": "originalfirst", "scripts": {}, "customMarkingAlgorithm": "", "matchMode": "exact", "showFeedbackIcon": true, "showCorrectAnswer": true, "extendBaseMarkingAlgorithm": true, "type": "patternmatch", "answer": "{prefix}"}], "sortAnswers": false}, {"unitTests": [], "variableReplacements": [], "marks": 0, "variableReplacementStrategy": "originalfirst", "scripts": {}, "customMarkingAlgorithm": "", "prompt": "

Write the statement in reverse Polish notation.

\n

[[0]]

", "showFeedbackIcon": true, "showCorrectAnswer": true, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "gaps": [{"unitTests": [], "variableReplacements": [], "marks": "2", "displayAnswer": "{postfix}", "variableReplacementStrategy": "originalfirst", "scripts": {}, "customMarkingAlgorithm": "", "matchMode": "exact", "showFeedbackIcon": true, "showCorrectAnswer": true, "extendBaseMarkingAlgorithm": true, "type": "patternmatch", "answer": "{postfix}"}], "sortAnswers": false}, {"unitTests": [], "variableReplacements": [], "marks": 0, "variableReplacementStrategy": "originalfirst", "scripts": {}, "customMarkingAlgorithm": "", "prompt": "

Compute the truth table for the statement.

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
 P Q R Statement 1 1 1 [[0]] 1 1 0 [[1]] 1 0 1 [[2]] 1 0 0 [[3]] 0 1 1 [[4]] 0 1 0 [[5]] 0 0 1 [[6]] 0 0 0 [[7]]

A tautology?

", "

Satisfiable?

", "

"], "prompt": "

Is the statement:

\n

", "shuffleChoices": false, "showFeedbackIcon": true, "showCorrectAnswer": true, "extendBaseMarkingAlgorithm": true, "type": "1_n_2", "displayType": "radiogroup", "displayColumns": 0}], "statement": "

Consider the following statement:

\n

{texify({infix},true)}

\n

N.B. In subsequent answers, you should write your statements as a descriptive string, with components separated by a space. For example, the statement $\\rightarrow P \\vee Q \\neg \\wedge R S$ would be entered as IMPLIES P OR Q NOT AND R S.

One can draw the parse tree for the statement: with the parse tree in hand, it is relatively straightforward to generate the Polish and reverse Polish notation statements.

\n

The truth table is simply a matter of evaluating the statement for all possible truth values of the arguments. Don't forget that $P\\rightarrow Q$ is equivalent to $(\\neg P)\\vee Q$.

\n

Recall that a statement is

\n
\n
• Tautological if the statement is true for all valuations;
• \n
• Satisfiable if the statement is true for at least one valuation;
• \n
• Contradictory if the statement is false for all valuations.
• \n
", "variables": {"noofvbls": {"templateType": "anything", "description": "

Determines how many different propositions are to be in the statement. noofvbls=3 gives a statement in P,Q,R; noofvbls=4 would give a statement in P,Q,R,S.

", "group": "Statements and Truth Tables", "name": "noofvbls", "definition": "3"}, "infix": {"templateType": "anything", "description": "

The statement in standard form.

", "group": "Statements and Truth Tables", "name": "infix", "definition": "string_from_tree(components,\"in\")"}, "taut": {"templateType": "anything", "description": "

A marking matrix for the final part: checking whether the statement is tautological (true for all valuations), satisfiable (true for some valuations), or contradictory (true for none).

", "group": "Statements and Truth Tables", "name": "taut", "definition": "if(sum(answer_output)=8,[2,0,0],if(sum(answer_output)=0,[0,0,2],[0,2,0]))"}, "components": {"templateType": "anything", "description": "

A list of parts of the statement. A component can be a proposition P,Q,R,S..., a binary operator AND, OR, IMPLIES, or the unary operator NOT. For details of how the components are ordered, see the Logic.js documentation.

", "group": "Statements and Truth Tables", "name": "components", "definition": "make_components(noofvbls*2,noofvbls,floor(noofvbls/2))"}, "prefix": {"templateType": "anything", "description": "

The statement in prefix (Polish) form.

", "group": "Statements and Truth Tables", "name": "prefix", "definition": "string_from_tree(components,\"pre\")"}, "postfix": {"templateType": "anything", "description": "

The statement in postfix (reverse Polish) form.

", "group": "Statements and Truth Tables", "name": "postfix", "definition": "string_from_tree(components,\"post\")"}, "truth_table": {"templateType": "anything", "description": "

Generated truth table from the statement: for details of the computation, see the Logic.js docs.

", "group": "Statements and Truth Tables", "name": "truth_table", "definition": "truth_table_results(components,3)"}, "answer_output": {"templateType": "anything", "description": "

A dirty fix to ensure that the truth table results are in [0,1] form, rather than [true,false].

", "group": "Statements and Truth Tables", "name": "answer_output", "definition": "map(if(truth_table[n],1,0),n,0..length(truth_table)-1)"}}, "functions": {}, "metadata": {"description": "

Gives a statement in standard notation: students must write it in Polish and reverse Polish notation, construct the truth table, and determine whether it is tautological, satisfiable, or contradictory.

\n

Uses the \"Logic\" extension: for details see the documentation.

", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "type": "question"}, {"name": "Equivalence", "extensions": ["Logic"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "contributors": [{"name": "Andrew Iskauskas", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/724/"}], "parts": [{"prompt": "

$\\Gamma$: $\\{$ {formula_tex} $\\}$

\n

$\\phi$: {texify({statement},false)}

\n

Variables: $[P,Q,R,S]$

\n

", "checkingAccuracy": 0.001, "vsetRange": [0, 1], "variableReplacements": [], "customMarkingAlgorithm": "", "marks": "4", "answer": "{cEx[0]}", "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "showPreview": true, "checkingType": "absdiff", "scripts": {"mark": {"order": "instead", "script": "/* Ideally, this would all be converted to a marking algorithm in the style of the Numbas 3.0 update */\n\n// Compare two arrays and return the number of matching elements.\nfunction howManyMatch(arr1,arr2)\n{\n if (arr1.length!=arr2.length)\n return 0;\n var tot = 0;\n for (i=0; ibestCred)\n bestCred = howManyMatch(testarr[j],sA);\n }\n this.setCredit(bestCred/4);\n\nthis.answered = true;"}}, "vsetRangePoints": 5, "extendBaseMarkingAlgorithm": true, "type": "jme", "unitTests": [], "expectedVariableNames": [], "checkVariableNames": false, "failureRate": 1}, {"prompt": "

$\\Gamma$: $\\{$ {formula_tex2} $\\}$

\n

$\\phi$: {texify({statement2},false)}

\n

Variables: $[P,Q,R,S,T]$

\n

", "checkingAccuracy": 0.001, "vsetRange": [0, 1], "variableReplacements": [], "customMarkingAlgorithm": "", "marks": "5", "answer": "{cEx2[0]}", "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "showPreview": true, "checkingType": "absdiff", "scripts": {"mark": {"order": "instead", "script": "// As in Part a).\n\nfunction howManyMatch(arr1,arr2)\n{\n if (arr1.length!=arr2.length)\n return 0;\n var tot = 0;\n for (i=0; ibestCred)\n bestCred = howManyMatch(testarr[j],sA);\n }\n this.setCredit(bestCred/5);\n\nthis.answered = true;"}}, "vsetRangePoints": 5, "extendBaseMarkingAlgorithm": true, "type": "jme", "unitTests": [], "expectedVariableNames": [], "checkVariableNames": false, "failureRate": 1}], "rulesets": {}, "variablesTest": {"maxRuns": "150", "condition": "length(formula_set)>=2 and length(formula_set2)>=2 and not(statement in formula_set) and not (statement2 in formula_set2) and not (length(cList)=0 and length(cList2)=0)"}, "metadata": {"description": "

Two questions on checking equivalence between a model and a statement. At least one of the two parts is guaranteed to admit a non-trivial solution (that is, actually have an instance where $\\Gamma$ holds and $\\phi$ doesn't.

\n

Uses the \"Logic\" extension: for details see the documentation.

", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "tags": [], "statement": "

For each of the following sets of formulae $\\Gamma$ and statement $\\phi$, determine whether $\\Gamma\\models\\phi$. If it does not, give an example of values for the variables for which the equivalence fails. If $\\Gamma\\models\\phi$, then enter '1' as a value for all variables.

\n

Enter your solution as an array of values: for example, if a counterexample is $v(P)=T,\\,v(Q)=F,\\,v(R)=T$, then your answer would be $[1,0,1]$.

", "functions": {"cleanup": {"type": "string", "definition": "// Simple function to replace IMPLIES in a statement, for valuation.\n// Note that this only works because IMPLIES only occurs in statements of the form \"P IMPLIES Q\"\n// More complicated statements (eg \"P IMPLIES (Q OR R)\") would not behave as expected.\nreturn statement.replace(/\$$(.) IMPLIES (.)\$$/g,\"((NOT \"+'$1'+\") OR \"+'$2)');", "parameters": [["statement", "string"]], "language": "javascript"}}, "ungrouped_variables": [], "advice": "

Recall that a set of statements $\\Gamma$ models a proposition $\\phi$ if the satisfaction of $\\Gamma$ implies the satisfaction of $\\phi$. Therefore, the easiest way to check such a system is to find any valuation in which $\\phi$ fails to hold, but $\\Gamma$ can be seen to be true.

\n

Consider $\\Gamma=\\{R\\vee P,\\,Q\\rightarrow R\\}$ and $\\phi=P\\wedge R$. Then we can see that $\\phi$ will be false if $P$ or $R$ are false. Since $\\Gamma$ contains $P\\vee R$, we need at least one to be true: taking $P=1,\\,Q=0$ and $R=0$ allows $\\Gamma$ to hold but $P\\wedge R$ to be false. The valuation is often not unique: if we instead took $P=0$, $R=1$ and then $Q$ could take either value.

", "variables": {"cList": {"definition": "filter((formula_output[x]=true and statement_output[x]=false),x,0..length(formula_output)-1)", "description": "

A list of indices for which gamma holds but the statement fails. The 'index' n is equivalent to a binary expression of 15-n, which gives a valuation of the variables.

", "templateType": "anything", "group": "Part 1", "name": "cList"}, "formula_statement": {"definition": "join(formula_set,\" AND \")", "description": "

A 'machine readable' version of gamma.

", "templateType": "anything", "group": "Part 1", "name": "formula_statement"}, "formula_statement2": {"definition": "join(formula_set2,\" AND \")", "description": "

A 'machine readable' version of gamma.

", "templateType": "anything", "group": "Part 2", "name": "formula_statement2"}, "formula_size": {"definition": "random(2..4)", "description": "

The number of statements in the formula, gamma.

", "templateType": "anything", "group": "Part 1", "name": "formula_size"}, "formula_set": {"definition": "distinct(make_model(formula_size,noofvbls))", "description": "

Generated list of statements in gamma.

", "templateType": "anything", "group": "Part 1", "name": "formula_set"}, "formula_output2": {"definition": "truth_table_results(cleanup(formula_statement2),noofvbls2)", "description": "

The truth table for the formula.

", "templateType": "anything", "group": "Part 2", "name": "formula_output2"}, "formula_size2": {"definition": "random(2..5)", "description": "

The number of statements in the formula, gamma.

", "templateType": "anything", "group": "Part 2", "name": "formula_size2"}, "formula_tex2": {"definition": "texify(join(formula_set2,\", \"),false)", "description": "

A version of gamma for display.

", "templateType": "anything", "group": "Part 2", "name": "formula_tex2"}, "noofvbls": {"definition": "4", "description": "

How many propositions are in the sets of statements: eg noofvbls=3 gives P,Q,R; noofvbls=4 gives P,Q,R,S.

", "templateType": "anything", "group": "Part 1", "name": "noofvbls"}, "formula_output": {"definition": "truth_table_results(cleanup(formula_statement),noofvbls)", "description": "

The truth table for the formula gamma.

", "templateType": "anything", "group": "Part 1", "name": "formula_output"}, "statement": {"definition": "make_model(1,noofvbls)[0]", "description": "

The statement with which to compare equivalence.

", "templateType": "anything", "group": "Part 1", "name": "statement"}, "formula_set2": {"definition": "make_model(formula_size2,noofvbls2)", "description": "

Generated list of statements in gamma.

", "templateType": "anything", "group": "Part 2", "name": "formula_set2"}, "cEx2": {"definition": "if(length(cList2)=0,[[1,1,1,1,1]],map(int_to_binary_array(31-cList2[n],5),n,0..length(cList2)-1))", "description": "

The result: if cList is empty, then the model is valid (and thus it returns [1,1,1,1,1]). If not, then this is a list of valuations for which the model fails

", "templateType": "anything", "group": "Part 2", "name": "cEx2"}, "statement_output": {"definition": "truth_table_results(cleanup(statement),noofvbls)", "description": "

The truth table for the statement

", "templateType": "anything", "group": "Part 1", "name": "statement_output"}, "noofvbls2": {"definition": "5", "description": "

How many propositions are in the sets of statements: eg noofvbls2=3 gives P,Q,R; noofvbls2=4 gives P,Q,R,S.

", "templateType": "anything", "group": "Part 2", "name": "noofvbls2"}, "statement2": {"definition": "make_model(1,noofvbls2)[0]", "description": "

The statement with which to compare equivalence.

", "templateType": "anything", "group": "Part 2", "name": "statement2"}, "cList2": {"definition": "filter((formula_output2[x] and not statement_output2[x]),x,0..length(formula_output2)-1)", "description": "

A list of indices for which gamma holds but the statement fails. The 'index' n is equivalent to a binary expression of 31-n, which gives a valuation of the variables.

", "templateType": "anything", "group": "Part 2", "name": "cList2"}, "statement_output2": {"definition": "truth_table_results(cleanup(statement2),noofvbls2)", "description": "

The truth table for the statement.

", "templateType": "anything", "group": "Part 2", "name": "statement_output2"}, "cEx": {"definition": "if(length(cList)=0,[[1,1,1,1]],map(int_to_binary_array(15-cList[n],4),n,0..length(cList)-1))", "description": "

The result: if cList is empty, then the model is valid (and thus it returns [1,1,1,1]). If not, then this is a list of valuations for which the model fails.

", "templateType": "anything", "group": "Part 1", "name": "cEx"}, "formula_tex": {"definition": "texify(join(formula_set,\", \"),false)", "description": "

A version of gamma for display.

", "templateType": "anything", "group": "Part 1", "name": "formula_tex"}}, "variable_groups": [{"variables": ["formula_size", "noofvbls", "formula_set", "statement", "formula_tex", "formula_statement", "formula_output", "statement_output", "cList", "cEx"], "name": "Part 1"}, {"variables": ["formula_size2", "noofvbls2", "formula_set2", "statement2", "formula_tex2", "formula_statement2", "formula_output2", "statement_output2", "cList2", "cEx2"], "name": "Part 2"}], "preamble": {"js": "", "css": ""}, "type": "question"}, {"name": "Disjunctive and Conjunctive Normal Forms", "extensions": ["Logic"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "contributors": [{"name": "Andrew Iskauskas", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/724/"}], "parts": [{"prompt": "

{texify({statement},true)}

\n

Disjunctive Normal Form: [[0]]

\n

Conjunctive Normal Form: [[1]]

", "variableReplacements": [], "customMarkingAlgorithm": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "unitTests": [], "gaps": [{"variableReplacements": [], "customMarkingAlgorithm": "", "marks": "2", "answer": "(?:\$$(?:(?:NOT .|.) AND )+(?:NOT .|.)\$$(?:\\s*OR\\s*\$$(?:(?:NOT .|.) AND )+(?:NOT .|.)\$$)*|(?:(?:(?:NOT .|.) AND )+(?:NOT .|.))|(?:NOT .|.))", "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "matchMode": "regex", "displayAnswer": "{dnf1}", "scripts": {"mark": {"order": "after", "script": "/*\nThis should really be converted into marking algorithm code, a la Numbas v3.0\n*/\n\n// Checks whether two arrays are the same.\nfunction sameArr(arr1,arr2)\n{\n if (arr1.length!=arr2.length)\n {\n return false;\n }\n for (i=0; i{texify({statement2},true)}

\n

Disjunctive Normal Form: [[0]]

\n

Conjunctive Normal Form: [[1]]

", "variableReplacements": [], "customMarkingAlgorithm": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "unitTests": [], "gaps": [{"variableReplacements": [], "customMarkingAlgorithm": "", "marks": "2", "answer": "(?:\$$(?:(?:NOT .|.) AND )+(?:NOT .|.)\$$(?:\\s*OR\\s*\$$(?:(?:NOT .|.) AND )+(?:NOT .|.)\$$)*|(?:(?:(?:NOT .|.) AND )+(?:NOT .|.))|(?:NOT .|.))", "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "matchMode": "regex", "displayAnswer": "{dnf2}", "scripts": {"mark": {"order": "after", "script": "// As in Part a)\nfunction sameArr(arr1,arr2)\n{\n if (arr1.length!=arr2.length)\n {\n return false;\n }\n for (i=0; iGenerate Disjunctive Normal Form and Conjunctive Normal Form for logical statements.

\n

Uses the \"Logic\" extension: for details see the documentation.

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "tags": [], "statement": "

Give the following statements in Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF).

\n

N.B. In subsequent answers, you should write your statements as a descriptive string, with components separated by a space. For example, the statement $(P \\vee Q \\wedge \\neg R) \\wedge (R \\vee P)$ would be entered as (P OR Q AND NOT R) AND (R OR P).

", "functions": {}, "ungrouped_variables": [], "advice": "

Suppose the statement was $(P \\vee \\neg Q)\\rightarrow (\\neg Q \\wedge \\neg P)$. The first step would be to generate the truth table for this statement: we can see that this will be

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
 P Q Statement 1 1 0 1 0 0 0 1 1 0 0 1
\n

To obtain the disjunctive normal form (DNF), we take the union of any valuations of $P$ and $Q$ that make the statement true. In this case, working down the rows of the truth table give

\n

$(\\neg P \\wedge Q)\\vee(\\neg P \\wedge \\neg Q).$

\n

The conjunctive normal form is given by the negation of the DNF of the negation of the statement: the cases for which the statement fails are $( P \\wedge Q)\\vee(P \\wedge \\neg Q)$. So negating this gives

\n

$\\neg((P \\wedge Q)\\vee(P \\wedge \\neg Q))=(\\neg P\\vee \\neg Q)\\wedge(\\neg P \\vee Q),$

\n

which is the CNF for the statement.

\n

Note that this method needn't give the simplest result: from inspecting the table the statement is equivalent to $\\neg P$, which is in DNF and CNF already!

", "variables": {"dnf2": {"definition": "normal_form(truth_table2,2,true)", "description": "

A disjunctive normal form for the statement. Not necessarily the most efficient; only used for answer display purposes.

", "templateType": "anything", "group": "Statement 2", "name": "dnf2"}, "cnf2": {"definition": "normal_form(truth_table2,2,false)", "description": "

A conjunctive normal form for the statement. Not necessarily the most efficient; only used for answer display purposes.

", "templateType": "anything", "group": "Statement 2", "name": "cnf2"}, "truth_table": {"definition": "truth_table_results(components,3)", "description": "

The truth table for the statement.

", "templateType": "anything", "group": "Statement 1", "name": "truth_table"}, "truth_table2": {"definition": "truth_table_results(components2,2)", "description": "

The truth table for the statement.

", "templateType": "anything", "group": "Statement 2", "name": "truth_table2"}, "statement": {"definition": "string_from_tree(components, \"in\")", "description": "

The components reexpressed in infix (standard) form.

", "templateType": "anything", "group": "Statement 1", "name": "statement"}, "components": {"definition": "make_components(5,3,2)", "description": "

Creates a list of components for the statement: for details on this, see the Logic.js docs.

", "templateType": "anything", "group": "Statement 1", "name": "components"}, "cnf1": {"definition": "normal_form(truth_table,3,false)", "description": "

A conjunctive normal form for the statement. Not necessarily the most efficient; only used for answer display purposes.

", "templateType": "anything", "group": "Statement 1", "name": "cnf1"}, "conversion2": {"definition": "map(if(truth_table2[n] = true, 1, 0), n, 0..length(truth_table2)-1)", "description": "

Quick-and-dirty way to ensure that the truth table output has elements [1,0], rather than [true, false].

", "templateType": "anything", "group": "Statement 2", "name": "conversion2"}, "statement2": {"definition": "string_from_tree(components2,\"in\")", "description": "

The components reexpressed in infix (standard) form.

", "templateType": "anything", "group": "Statement 2", "name": "statement2"}, "dnf1": {"definition": "normal_form(truth_table,3,true)", "description": "

A disjunctive normal form for the statement. Not necessarily the most efficient; only used for answer display purposes.

", "templateType": "anything", "group": "Statement 1", "name": "dnf1"}, "components2": {"definition": "make_components(3,2,2)", "description": "

Creates a list of components for the statement: for details on this, see the Logic.js docs.

", "templateType": "anything", "group": "Statement 2", "name": "components2"}, "conversion": {"definition": "map(if(truth_table[n]=true,1,0),n,0..length(truth_table)-1)", "description": "

Quick-and-dirty way to ensure that the truth table output has elements [1,0], rather than [true, false].

", "templateType": "anything", "group": "Statement 1", "name": "conversion"}}, "variable_groups": [{"variables": ["components", "statement", "truth_table", "conversion", "dnf1", "cnf1"], "name": "Statement 1"}, {"variables": ["components2", "statement2", "truth_table2", "conversion2", "dnf2", "cnf2"], "name": "Statement 2"}], "preamble": {"js": "", "css": ""}, "type": "question"}, {"name": "Propositional Formulae", "extensions": ["Logic"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "contributors": [{"name": "Andrew Iskauskas", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/724/"}, {"name": "Alexander Hague", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2654/"}], "variable_groups": [{"variables": ["TT1", "dnf1", "cnf1", "output1"], "name": "(a)"}, {"variables": ["TT2", "dnf2", "cnf2", "output2"], "name": "(b)"}, {"variables": ["TT3", "dnf3", "cnf3", "output3"], "name": "(c)"}, {"variables": ["TT4", "dnf4", "cnf4", "output4"], "name": "(d)"}], "parts": [{"answer": ".*", "matchMode": "regex", "unitTests": [], "showFeedbackIcon": true, "showCorrectAnswer": true, "scripts": {"mark": {"order": "instead", "script": "/*\nShould be converted to marking algorithm, a la Numbas v3.0\n*/\n\n// Checks whether two arrays are the same.\nfunction sameArr(arr1,arr2)\n{\n if (arr1.length!=arr2.length)\n {\n return false;\n }\n for (i=0; iThere are a number of ways to approach this. The most algorithmic is to apply the method used to get disjunctive and conjunctive normal form, as seen before. From this expression, it may be possible to simplify: for example the statement $(P \\wedge Q \\wedge R)\\vee(P \\wedge Q \\wedge \\neg R)$ clearly allows for both valuations of $R$, so is equivalent to the statement $P \\wedge Q$. You may be able to spot such simplifications from the truth table: for example a truth table

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
 P Q R Statement 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1
\n

values as true when $R$ is true, and also when all parameters are false. So one could write $R\\vee(\\neg P \\wedge \\neg Q \\wedge \\neg R)$.

", "rulesets": {}, "metadata": {"description": "

From a truth table, find a statement in three variables that satisfies it.

\n

Uses the \"Logic\" extension: for details see the documentation.

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "

Find propositional formulae for the following truth tables.

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
 P Q R (a) (b) (c) (d) 1 1 1 {TT1[0]} {TT2[0]} {TT3[0]} {TT4[0]} 1 1 0 {TT1[1]} {TT2[1]} {TT3[1]} {TT4[1]} 1 0 1 {TT1[2]} {TT2[2]} {TT3[2]} {TT4[2]} 1 0 0 {TT1[3]} {TT2[3]} {TT3[3]} {TT4[3]} 0 1 1 {TT1[4]} {TT2[4]} {TT3[4]} {TT4[4]} 0 1 0 {TT1[5]} {TT2[5]} {TT3[5]} {TT4[5]} 0 0 1 {TT1[6]} {TT2[6]} {TT3[6]} {TT4[6]} 0 0 0 {TT1[7]} {TT2[7]} {TT3[7]} {TT4[7]}
\n

As always, you should write your statements as a descriptive string, with components separated by a space. For example, the statement $(P \\vee Q \\wedge \\neg R) \\wedge (R \\vee P)$ would be entered as (P OR Q AND NOT R) AND (R OR P).

", "variables": {"output4": {"templateType": "anything", "description": "

Takes the simplest of the two of dnf4, cnf4. For answer display purposes only.

", "definition": "if (length(dnf4)>length(cnf4), cnf4, dnf4)", "name": "output4", "group": "(d)"}, "dnf2": {"templateType": "anything", "description": "

Generates a disjunctive normal form based on TT2.

", "definition": "if (sum(TT2)=0, \"P AND NOT P\", normal_form(TT2,3,true))", "name": "dnf2", "group": "(b)"}, "cnf1": {"templateType": "anything", "description": "

Generates a conjunctive normal form based on TT1

", "definition": "if (sum(TT1)=8, \"P OR NOT P\", normal_form(TT1,3,false))", "name": "cnf1", "group": "(a)"}, "cnf2": {"templateType": "anything", "description": "

Generates a conjunctive normal form based on TT2.

", "definition": "if (sum(TT2)=8, \"P OR NOT P\", normal_form(TT2,3,false))", "name": "cnf2", "group": "(b)"}, "TT2": {"templateType": "anything", "description": "

A random collection of true and false.

", "definition": "map(random([0,1]),n,0..7)", "name": "TT2", "group": "(b)"}, "output1": {"templateType": "anything", "description": "

Takes the simplest of the two of dnf1, cnf1. For answer display purposes only.

", "definition": "if(length(dnf1)>length(cnf1),cnf1,dnf1)", "name": "output1", "group": "(a)"}, "cnf3": {"templateType": "anything", "description": "

Generates a conjunctive normal form based on TT3.

", "definition": "if (sum(TT3)=8, \"P OR NOT P\", normal_form(TT3,3,false))", "name": "cnf3", "group": "(c)"}, "TT1": {"templateType": "anything", "description": "

A random collection of true and false.

", "definition": "map(random([0,1]),n,0..7)", "name": "TT1", "group": "(a)"}, "TT3": {"templateType": "anything", "description": "

A random collection of true and false.

", "definition": "map(random([0,1]),n,0..7)", "name": "TT3", "group": "(c)"}, "dnf4": {"templateType": "anything", "description": "

Generates a disjunctive normal form based on TT4.

", "definition": "if (sum(TT4)=0, \"P AND NOT P\", normal_form(TT4,3,true))", "name": "dnf4", "group": "(d)"}, "output3": {"templateType": "anything", "description": "

Takes the simplest of the two of dnf3, cnf3. For answer display purposes only.

", "definition": "if(length(dnf3)>length(cnf3),cnf3,dnf3)", "name": "output3", "group": "(c)"}, "output2": {"templateType": "anything", "description": "

Takes the simplest of the two of dnf2, cnf2. For answer display purposes only.

", "definition": "if(length(dnf2)>length(cnf2),cnf2,dnf2)", "name": "output2", "group": "(b)"}, "dnf3": {"templateType": "anything", "description": "

Generates a disjunctive normal form based on TT3.

", "definition": "if(sum(TT3)=0, \"P AND NOT P\", normal_form(TT3,3,true))", "name": "dnf3", "group": "(c)"}, "dnf1": {"templateType": "anything", "description": "

Generates a disjunctive normal form based on TT1.

", "definition": "if (sum(TT1)=0, \"P AND NOT P\", normal_form(TT1,3,true))", "name": "dnf1", "group": "(a)"}, "cnf4": {"templateType": "anything", "description": "

Generates a conjunctive normal form based on TT4.

", "definition": "if (sum(TT4)=8, \"P OR NOT P\", normal_form(TT4,3,false))", "name": "cnf4", "group": "(d)"}, "TT4": {"templateType": "anything", "description": "

A random collection of true and false.

", "definition": "map(random([0,1]),n,0..7)", "name": "TT4", "group": "(d)"}}, "preamble": {"js": "", "css": ""}, "tags": [], "ungrouped_variables": [], "type": "question"}]}], "name": "Logic Node Demo", "feedback": {"advicethreshold": 0, "showanswerstate": true, "allowrevealanswer": true, "feedbackmessages": [], "showactualmark": true, "showtotalmark": true, "intro": ""}, "percentPass": 0, "navigation": {"browse": true, "allowregen": true, "showresultspage": "oncompletion", "showfrontpage": true, "preventleave": true, "onleave": {"action": "none", "message": ""}, "reverse": true}, "showQuestionGroupNames": false, "timing": {"timeout": {"action": "none", "message": ""}, "allowPause": true, "timedwarning": {"action": "none", "message": ""}}, "duration": 0, "type": "exam", "contributors": [{"name": "Andrew Iskauskas", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/724/"}], "extensions": ["Logic"], "custom_part_types": [], "resources": []}